java - 采访: Remove Loop in linked list - 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)将在有限步数之后最终指向同一个元素。有趣的是，可以证明它们相遇的元素将与 到 循环 起点的距离相同(继续以相同的正向遍历列表)作为起点循环的 head 是列表的。也就是说，如果列表的线性部分有 k 元素，则两个指针将在长度为 m 的循环内的一点 m-k 相遇从循环或 k 元素的开始到循环的“结束”(当然，这是一个循环，因此它没有“结束” - 它只是“开始”)。这为我们提供了一种找到循环起点的方法:

2. 一旦检测到循环，让 p2 保持指向上述步骤的循环终止的元素，但重置 p1 使其指向返回到列表的首位。现在，一次将每个指针移动一个元素。由于 p2 在循环内部开始，它将继续循环。在 k 步之后(等于循环开始到链表头部的距离)，p1 和 p2 将再次相遇。这将为您提供循环开始的引用。

3. 现在很容易设置 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可能有助于第二部分背后的原因:

Assume the length of the cycle is M, and the length of the rest of the linked list is L. Let's figure out what is the position in the cycle when t1/t2 first meet?

Define the first node in the cycle is position 0, following the links we have position 1, 2,..., up to M-1. ( when we walk in the cycle, our current position is (walk_length) mod M, right?) Suppose t1/t2 first meet at position p, then their travel time are the same, (L+k1*M+p)/v = (L+k2*M+p)/2v for some k1

So it concludes that if t1 start from p, t2 start from head and move at the same speed, then will grantee to meet at position 0, the first node of the cycle. 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还引用了一本采访书中的解释