访问：删除链接列表中的循环 - Java [英] Interview: Remove Loop in linked list - Java

问题描述

我在采访中被问到这个问题：如何检测链表中的循环，我解决了这个问题，但是立即访问者问我如何删除链表中的循环。我感到困惑。

I was asked this question in interview: "How to detect the loop in linked list?", I solved this but immediately the interviewer asked me how do I remove the loop in a linked list. I fumbled.

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

So any pointers on how to solve this, may be pseudo code, or method definition?

我对Java很熟悉，所以我在java下标记了这个问题。

I'm comfortable with Java so I have tagged this question under java.

对于Instance，此链接列表有一个循环

For Instance this linked list has a loop

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

推荐答案

这个问题有两个部分：

1. 检测列表中是否有循环


2. 确定循环的开始

一旦你知道循环开始的地方，很容易以识别列表中的最后一个元素，因为它是循环开始后的列表中的元素，最终指向循环的开始。将此元素的下一个指针/引用设置为 null 来校正循环链接列表（而不是循环链接列表，这是最后一个元素指向首先 - 这将是循环列表的具体实例。）

Once you know where the loop starts, it's easy to identify the last element in the list since it's the element in the list following the start of the loop that ends up pointing back to the start of the loop. It is then trivial to set the next pointer/reference of this element to null to correct the cyclic link list (not circular linked list which is where the last elements points back to the first - this would be a specific instance of cyclic lists).

1. p1 和 p2 ）将指向相同的元素有限数量的步骤。有趣的是，可以证明，他们相遇的元素将与循环的开始相同的距离（继续以相同的向前方向遍历列表）作为开始的循环是列表的头。也就是说，如果列表的线性部分具有 k 元素，则两个指针将在长度 m 在循环开头的 mk 或 k 元素到循环'（of当然，这是一个循环，所以它没有'结束' - 这只是'开始'再一次）。这样我们可以找到循环的开始：

1. Floyd's cycle detect algorithm, also called the tortoise and hare algorithm as it involves using two pointers/references that move at different speeds, is one way of detecting the cycle. If there is a cycle, the two pointers (say p1 and p2) will end up pointing to the same element after a finite number of steps. Interestingly, it can be proved that the element at which they meet will be the same distance to the start of the loop (continuing to traverse the list in the same, forward direction) as the start of the loop is to the head of the list. That is, if the linear part of the list has k elements, the two pointers will meet inside the loop of length m at a point m-k from the start of the loop or k elements to the 'end' of the loop (of course, it's a loop so it has no 'end' - it's just the 'start' once again). And that gives us a way to find the start of the loop:

一旦检测到一个循环，让 p2 保持指向上述步骤的循环终止但重置 p1 的元素，以便它指向列表的头部。现在，每个指针一次移动一个元素。由于 p2 开始循环，它将继续循环。之后 k steps（等于从列表头开始循环的距离）， p1 和 p2 将再次相遇。这将为您提供循环的开始。

Once a cycle has been detected, let p2 remain pointing to the element where the loop for the step above terminated but reset p1 so that it's pointing back to the head of the list. Now, move each pointer one element at a time. Since p2 began inside the loop, it will continue looping. After k steps (equal to the distance of the start of the loop from the head of the list), p1 and p2 will meet again. This will give you a reference to the start of the loop.

现在很容易设置 p1 （或 p2 ）指向启动循环的元素并遍历循环，直到 p1 结束指向起始元素。此时， p1 正在引用最后元素列表，它的下一个指针可以设置为 null 。 p>

It is now easy to set p1 (or p2) to point to the element starting the loop and traverse the loop until p1 ends up pointing back to the starting element. At this point p1 is referencing the 'last' element list and it's next pointer can be set to null.

---

以下是一些简单而肮脏的Java代码，假设 Node s，其中 Node 有一个下一个引用。这可以被优化，但它应该给你的基本思想：

---

Here's some quick and dirty Java code assuming a linked list of Nodes where a Node has a next reference. This could be optimized but it should give you the basic idea:

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 might help the why behind Part II:

假设循环的长度为M，
，
链接列表的其余部分的长度为L.我们计算出
在当
t1 / t2第一次满足时，循环？

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?

定义循环中的第一个节点是
位置0，跟随链接我们
具有位置1,2，...，直到M-1。 （
当我们在循环中行走时，我们当前的
位置是（walk_length）mod M，
right？）假设t1 / t2首先满足
位置p，然后他们的旅行时间是
相同，（L + k1 * M + p）/ v =（L + k2 * M + p）/ 2v
对于某些k1

因此，如果t1从
p开始，t2从头开始，以
相同的速度移动，则将允许在0位满足
，
的第一个节点周期。 QED。

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


• 解释循环链表中查找周期开始节点的工作原理？


• 检测链表中循环开始的证明


• Hristo对此问题的回答在这个页面上还引用了一个访谈书的解释

• 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 also quotes an explanation from an interview book

这篇关于访问：删除链接列表中的循环 - Java的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！