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

Question

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

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

我对Java很满意，因此已在Java下标记了这个问题。

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

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

Answer 1

此问题有两个部分：

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

一旦知道了循环的开始位置，就很容易识别列表中的最后一个元素，因为它是循环开始之后的列表中的元素，最终指向循环的开始。然后，很容易设置该元素的下一个指针/引用null以更正循环链接列表（不是循环链接列表，后者是最后一个元素指向第一个元素的位置-
这将是循环列表的特定实例）。

1. 弗洛伊德（Floyd）的周期检测算法（也称为乌龟和野兔算法），因为它涉及使用以不同速度移动的两个指针/引用，是检测周期的一种方法。如果存在一个循环，则在有限数量的步骤之后，两个指针（say p1和p2）将最终指向同一元素。有趣的是，可以证明它们相遇的元素 到 循环* 起点的距离 是 _相同的 （继续以相同的向前方向遍历列表），因为循环起点是 列表 的 _ 开头* 。也就是说，如果列表的线性部分包含k元素，则两个指针将在长度循环内的m某个点相遇m-k从循环或k元素的开始到循环的“结束”（当然，这是一个循环，因此它没有“结束”-再次只是“开始”）。这为我们提供了找到循环起点的方法：

2. 一旦检测到一个循环，让我们p2继续指向上面步骤的循环终止但重置的元素，以p1使其指向列表的开头。现在，将每个指针一次移动一个元素。自从p2在循环内开始以来，它将继续循环。之后的k步骤（等于循环开始点与列表开头的距离），p1然后p2会再次碰面。这将为您提供循环开始的参考。

3. 现在很容易设置p1（或p2）指向开始循环的元素并遍历循环，直到p1最终指向开始元素为止。此时p1正在引用“最后一个”元素列表，并且其下一个指针可以设置为null。

这是一些快速且肮脏的Java代码，假定Nodes 的链表，其中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 =（L + k2 * M + p）/
2v对于某些k1

因此得出的结论是，如果t1从p开始，t2从头部开始并以相同的速度移动，则被授予者将在循环的第一个节点0处相遇。QED。