访谈:删除链表中的循环 - Java

Question

我在采访中被问到这个问题:"如何检测链表中的循环？",我解决了这个问题,但是面试官立刻问我如何删除链表中的循环.我摸索着.

那么关于如何解决这个问题的任何指针都可能是伪代码或方法定义？

我对Java很满意所以我在java下标记了这个问题.

对于实例,此链接列表具有循环

 0--->1---->2---->3---->4---->5---->6
                  ?                 |
                  |                 ?
                 11<—-22<—-12<—-9<—-8

Answer 1

这个问题有两个部分:

1. 检测列表中是否存在循环
2. 确定循环的开始

一旦你知道循环的开始位置,很容易识别列表中的最后一个元素,因为它是循环开始后列表中的元素,最后指向循环的开始.然后,设置此元素的下一个指针/引用null以更正循环链接列表(不是循环链接列表,这是最后一个元素指向第一个元素的位置 - 这将是循环列表的特定实例)是微不足道的.

1. Floyd的循环检测算法,也称为乌龟和野兔算法,因为它涉及使用以不同速度移动的两个指针/参考,是检测循环的一种方式.如果有一个周期,两个指针(说p1和p2)最终将有限数量的步骤之后指向相同的元件.有趣的是,可以证明它们遇到的元素与循环开始的距离相同(继续以相同的向前方向遍历列表),因为循环的开始是列表的开头.也就是说,如果列表的线性部分有k元素,那么两个指针将在从循环开始或元素到循环的"结束"的m某个点的长度循环内相遇(当然,它是一个循环所以它没有'结束' - 它只是再次'开始'.这为我们提供了一种找到循环开始的方法:m-kk

2. 一旦检测到一个循环,让我们p2保持指向上面步骤的循环终止的元素,但是重置,p1以便它指向返回列表的头部.现在,一次将每个指针移动一个元素.从p2循环内部开始,它将继续循环.在k步骤之后(等于循环开始距离列表头部的距离),p1并将p2再次相遇.这将为您提供循环开始的参考.

3. 现在可以很容易地设置p1(或p2)指向开始循环的元素并遍历循环,直到p1最终指向起始元素.此时p1引用'last'元素列表,它的下一个指针可以设置为null.

这里有一些快速而脏的Java代码,假设一个链接列表,Node其中a Node有一个next引用.这可以优化,但它应该给你基本的想法:

Node slow, fast, start;
fast = slow = head;

//PART I - Detect if a loop exists
while (true)
{
    // fast will always fall off the end of the list if it is linear
    if (fast == null || fast.next == null)
    {
        // no loop
        return;
    }
    else if (fast == slow || fast.next == slow)
    {
        // detected a loop
        break;
    }
    else
    {
        fast = fast.next.next; // move 2 nodes at at time
        slow = slow.next; // move 1 node at a time
    }
}

//PART II - Identify the node that is the start of the loop
fast = head; //reset one of the references to head of list

//until both the references are one short of the common element which is the start of the loop
while(fast.next != slow.next) 
{
    fast = fast.next;
    slow = slow.next;
}

start = fast.next;

//PART III - Eliminate the loop by setting the 'next' pointer 
//of the last element to null
fast = start;
while(fast.next != start)
{
    fast = fast.next;
}

fast.next = null; //break the loop

这种解释可能有助于第二部分背后的原因:

假设循环的长度是M,并且链表的其余部分的长度是L.让我们弄清楚当t1/t2第一次遇到时循环中的位置是什么？

定义循环中的第一个节点是位置0,跟随链接我们有位置1,2,...,直到M-1.(当我们走进循环时,我们当前的位置是(walk_length)mod M,对吗？)假设t1/t2首先在位置p处相遇,那么它们的行程时间是相同的,(L + k1*M + p)/ v对于某些k1,=(L + k2*M + p)/ 2v

因此得出结论,如果t1从p开始,t2从头开始并以相同的速度移动,那么将被授予在位置0(周期的第一个节点)处相遇.QED.

更多参考:

• http://www.quora.com/How-does-Floyds-cycle-finding-algorithm-work
• 解释循环链表中查找循环开始节点的工作原理？
• 检测链表中循环开始的证明
• Hristo在这个页面上对这个问题的回答也引用了一本采访书的解释

Answer 2

解决方案1 - 由职业杯和"破解编码面试"一书提供:

public static LinkedListNode findStartOfLoop(LinkedListNode head) {
    LinkedListNode n1 = head;
    LinkedListNode n2 = head; 

    // find meeting point using Tortoise and Hare algorithm
    // this is just Floyd's cycle detection algorithm
    while (n2.next != null) { 
        n1 = n1.next; 
        n2 = n2.next.next; 
        if (n1 == n2) { 
            break; 
        }
    }

    // Error check - there is no meeting point, and therefore no loop
    if (n2.next == null) {
        return null;
    }

    /* Move n1 to Head. Keep n2 at Meeting Point.  Each are k steps
    /* from the Loop Start. If they move at the same pace, they must
     * meet at Loop Start. */
    n1 = head; 
    while (n1 != n2) { 
        n1 = n1.next; 
        n2 = n2.next; 
    }
    // Now n2 points to the start of the loop.
    return n2;
}

这个解决方案的解释直接来自本书:

如果我们移动两个指针,一个速度为1,另一个速度为2,如果链表有循环,它们将会结束.为什么？想想两辆车在赛道上行驶; 更快的汽车将永远通过较慢的汽车!

这里棘手的部分是找到循环的开始.想象一下,作为一个类比,两个人在赛道上比赛,一个赛跑的速度是另一个赛车的两倍.如果他们在同一个地方开始,他们下一次会什么时候见面？接下来他们将在下一圈开始时见面.

现在,让我们假设Fast Runner在n步圈上有一个k米的起跑线.他们什么时候下次见面？他们将在下一圈开始前达到k米.(为什么？快跑者会做出k + 2(n-k)步骤,包括它的头部开始,而慢跑者会做出n-k步骤.在循环开始之前两个步骤都是k步).

现在,回到问题,当Fast Runner(n2)和Slow Runner(n1)在我们的循环链表中移动时,当n1进入时,n2将在循环上有一个开头.具体来说,它将具有k的头部起点,其中k是循环之前的节点数.由于n2具有k个节点的头部起始,因此n1和n2将在循环开始之前与k个节点相遇.

所以,我们现在知道以下内容:

1. 头是来自LoopStart的k个节点(根据定义)
2. MeetingPoint for n1和n2是来自LoopStart的k个节点(如上所示)

因此,如果我们将n1移回Head并在MeetingPoint保持n2,并以相同的速度移动它们,他们将在LoopStart会面

解决方案2 - 礼貌我:)

public static LinkedListNode findHeadOfLoop(LinkedListNode head) {

    int indexer = 0;
    Map<LinkedListNode, Integer> map = new IdentityHashMap<LinkedListNode, Integer>();
    map.put(head, indexer);
    indexer++;

    // start walking along the list while putting each node in the HashMap
    // if we come to a node that is already in the list, 
    // then that node is the start of the cycle 
    LinkedListNode curr = head;
    while (curr != null) {

        if (map.containsKey(curr.next)) {
            curr = curr.next;
            break;
        }
        curr = curr.next;
        map.put(curr, indexer);
        indexer++;
    }
    return curr;
}

我希望这有帮助.
斯托伊奇

Answer 3

这种反应并不是为了争夺答案,而是为了解释乌龟和野兔算法中两个节点的会议.

1. 两个节点最终都会进入循环.因为一个比另一个(S)移动得更快(F),所以(F)最终会绕圈(S).

2. 如果循环的开始位于列表的头部,则(F)必须在列表的头部回到(S).这只是因为(F)的速度是2X(S); 如果它是3倍,那么就不会是真的.这是正确的,因为当(S)完成半圈时(F)完成一圈,所以当(S)完成其第一圈时,(F)完成两圈 - 并且在(S)回到循环开始时.

3. 如果循环的开始不在列表的头部,则在时间(S)进入循环时,(F)在循环中具有(k)节点的头部开始.因为(S)的速度一次只有一个节点,它将在循环开始时在(k)节点处满足(F) - 如,(k)在到达开始之前的更多步骤,而不是(k)步骤之后开始.如果(S)的速度不是1并且速度比在(F)和(S)之间不是2:1,则不是这样.

   3.1.这是解释一下有点棘手的地方.我们可以同意(F)将继续研磨(S)直到它们最终满足(参见上面的1),但是为什么在循环开始的(k)节点处？考虑以下等式,其中M是节点的数量或循环的距离,k是起始点(F); 等式表示(F)左边给定时间t的行进距离(S)在右边的行进距离:

   d_F(t)= 2*d_S(t)+ k

   因此,当(S)进入循环并且在循环中行进了0距离时,(F)仅行进了(k)距离.到时间d_S = M-k,d_F = 2M-k.因为考虑到M代表循环中单圈的总距离,我们还必须使用模数运算,任何整个M(无余数)的(F)和(S)的位置都是0.那么就... POSITION(或差异),这留下k(或更确切地说,-k).

   最后,(S)和(F)将在远离循环开始的位置(0-k)或(k)节点处相遇.

4. 鉴于上面的[3],因为(k)代表头部开始(F),并且因为(F)已经行进了2倍距离(S)从列表的头部进入循环,(k)也表示距列表开始的距离,然后表示循环的开始.

这里有点晚了,所以我希望我能有效地表达出来.让我知道其他情况,我会尝试更新我的回复.

Answer 4

如果允许使用身份哈希映射(例如IdentityHashMap),这非常容易解决.但它确实使用了更多的空间.

遍历节点列表.对于遇到的每个节点,将其添加到身份映射.如果节点已经存在于身份映射中,则列表具有循环链接,并且已知此冲突之前的节点(在移动之前检查或保留"最后一个节点") - 只需根据需要设置"下一个"打破这个循环.

遵循这个简单的方法应该是一个有趣的练习:代码留给读者练习.

快乐的编码.