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

Question

我在面试中被问到这个问题：“如何检测链表中的循环？”，我解决了这个问题，但面试官立即问我如何删除链表中的循环。我笨手笨脚的。

那么关于如何解决这个问题的任何建议，可能是伪代码，或者是方法定义？

我对java很满意，所以我把这个问题放在了Java下面。

例如，这个链表有一个循环

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

Answer 1

这个问题有两个部分：

1. 检测列表中是否有循环
2. 识别循环的开始

一旦知道了循环的开始位置，就很容易识别列表中的最后一个元素，因为它是列表中循环开始后的元素，最后指向循环的开始。然后，很容易将这个元素的下一个指针/引用设置为null来纠正循环链表(而不是循环链表，它是最后一个元素指向第一个元素的地方-这将是循环列表的一个特定实例)。

1. Floyd's cycle detect algorithm, also called the tortoise and hare algorithm是检测循环的一种方法，因为它涉及到使用以不同速度移动的两个指针/引用。如果有一个循环，那么两个指针(比如p1和p2)将在有限步之后指向同一个元素。有趣的是，可以证明它们相遇的元素到循环的起点(继续以相同的前进方向遍历列表)的距离与循环起点到列表的头的距离相同。也就是说，如果列表的线性部分有k元素，这两个指针将在长度为m的循环内从循环开始的点m-k或k元素到循环的“end”相交(当然，这是一个循环，所以它没有“end”-它又是“start”)。这给了我们一种找到循环开始的方法：，

，

1. 一旦检测到循环，让p2保持指向上面步骤的循环终止的元素，但重置p1，使其指向列表的开头。现在，一次移动一个指针元素。由于p2是从循环内部开始的，因此它将继续循环。在k步之后(等于循环开始到列表头部的距离)，p1和p2将再次相遇。
2. 现在很容易将p1 (或p2)设置为指向开始循环的元素，然后遍历循环，直到p1指向开始的元素。此时，p1引用了'last‘元素列表，它的下一个指针可以设置为null.

下面是一些快速而肮脏的Java代码，假设一个Node链表，其中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

This explanation可能有助于了解第二部分背后的原因：

假设周期的长度是M，链表的其余部分的长度是L。让我们计算一下t1/t2第一次相遇时，周期中的位置是什么？

定义周期中的第一个节点是位置0，沿着我们有位置1，2，...的链接直到M-1。(当我们在循环中行走时，我们的当前位置是(walk_length) mod M，对吗？)假设t1/t2首先在位置p相遇，则它们的行进时间相同，(L+k1*M+p)/v = (L+k2*M+p)/2v对于某些k1So，它的结论是:如果t1从p开始，t2从头部开始并以相同的速度移动，则将被允许在位置0，即周期的第一个节点相遇。QED。

更多参考资料：

• http://www.quora.com/How-does-Floyds-cycle-finding-algorithm-work
• Explain how finding cycle start node in cycle linked list work?
• Proof of detecting the start of cycle in linked list
• Hristo's answer to this question on this page还引用了一本访谈书

中的一段解释

Answer 2

解决方案1 -由Career Cup and "Cracking the Coding Interview" book提供

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米。(为什么？Fast Runner会做k+ 2(n - k)步，包括它的头开始，而Slow Runner会做n-k步，这两个步骤都是循环开始前的k步)。

现在，回到问题上来，当快速跑步者( n2 )和慢跑者( n1 )在我们的循环链表中移动时，当n1进入时，n2将在循环中领先。具体地说，它的开头是k，其中k是循环之前的节点数。由于n2的起始节点为k个，因此n1和n2将在循环开始之前与k个节点相遇。

因此，我们现在知道以下内容：

1. Head是来自LoopStart的k个节点(根据定义)，
2. MeetingPoint

n1和n2是来自LoopStart的k个节点(如上所示)

因此，如果我们将n1移回Head，并将n2留在MeetingPoint，并以相同的速度移动它们，它们将在LoopStart相遇

Solution 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. 两个节点最终都将进入循环。因为一个循环的速度(F)比另一个(S)快，所以(F)最终会绕过(S)。
2. 如果循环的开始在列表的头部，(F)必须在列表的头部满足(S)。这只是因为(F)的速度是2X (S)的；如果它是3X，那么这就不是真的。这是正确的，因为(F)在(S)完成半圈时完成一圈，因此当(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)；方程表示给定时间t在左边的距离(F)，用右边的(S)行驶的距离表示：

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

因此，当(S)进入循环并在循环中行进0距离时，(F)仅行进(k)距离。时间d_S =M- k，d_F = 2M - k。因为考虑到M代表循环中单圈的总距离，我们还必须使用模数学，所以(F)和(S)在任何整数M(没有余数)的位置是0。因此，就位置(或微分)而言，这就剩下k(或者更确切地说，-k)。

因此，最后，(S)和(F)将在距离循环开始位置(0 - k)或(k)节点处相遇。上面给出的

• 为3，因为(k)表示头部开始(F)，并且由于(F)从列表头部进入循环的距离(S)行进了2倍，(k)也表示到列表开始的距离，然后表示循环的开始。

这里有点晚了，所以我希望我已经有效地表达了。如果不是这样，请告诉我，我会尝试更新我的回复。