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

问题描述

我在面试中被问到这个问题:如何检测链表中的循环?"，我解决了这个问题，但面试官立即问我如何删除链表中的循环.我摸索了.

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

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

例如这个链表有一个循环

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

解决方案

这个问题有两个部分:

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

一旦您知道循环从哪里开始，就很容易识别列表中的最后一个元素，因为它是列表中循环开始之后的元素，最终指向循环的开始.然后将这个元素的下一个指针/引用设置为 null 以纠正循环链表(不是循环链表，它是最后一个元素指向第一个元素的地方 - 这将是一个循环列表的具体实例).

1. Floyd 的循环检测算法，也称为龟兔算法它涉及使用两个以不同速度移动的指针/参考，是检测循环的一种方法.如果存在循环，则两个指针(例如 p1 和 p2)将在有限步数后最终指向同一个元素.有趣的是，可以证明它们相遇的元素将到循环开始的距离相同(继续以相同的、向前的方向遍历列表)作为开始循环指向列表的头部.也就是说，如果列表的线性部分有 k 个元素，那么两个指针会在长度为 m 的循环内在一个点 mk 相遇从循环的开始或 k 元素到循环的结束"(当然，这是一个循环，所以它没有结束"——它只是又一次的开始").这给了我们一种找到循环开始的方法:

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

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

<小时>

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

节点慢，快，启动；快 = 慢 = 头；//PART I - 检测是否存在循环而(真){//如果是线性的，fast 总是会从列表的末尾掉下来if (fast == null || fast.next == null){//没有循环返回;}否则如果(快==慢||快.下一个==慢){//检测到一个循环休息;}别的{fast = fast.next.next;//同时移动 2 个节点慢 = 慢.下一个；//一次移动 1 个节点}}//PART II - 识别作为循环开始的节点快 = 头；//重置对列表头的引用之一//直到两个引用都缺少作为循环开始的公共元素while(fast.next !=slow.next){快 = 快.下一个；慢 = 慢.下一个；}开始=fast.next;//第三部分 - 通过设置next"指针消除循环//最后一个元素为null快 = 开始；while(fast.next != start){快 = 快.下一个；}fast.next = null;//打破循环

<小时>

这个解释可能有助于第二部分背后的原因:<块引用>

假设循环的长度为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.

更多参考:

• http://www.quora.com/How-do-Floyds-cycle-finding-algorithm-work
• 说明如何在循环链表工作?
• 检测开始的证明链表中的循环
• Hristo 在此页面上对此问题的回答 还引用了一本采访书中的解释

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?

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

For Instance this linked list has a loop

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

解决方案

There are two parts to this problem:

1. Detect if there is a loop in the list
2. Identify the start of the loop

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. 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:

2. 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.

3. 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.

---

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:

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.

More references:

• 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屋！