采访：删除链接列表中的循环 – Java
我在采访中被问到这个问题：“如何检测链表中的循环？”，我解决了这个问题，但是面试官立即问我如何去除链表中的循环。 我失手了
那么如何解决这个问题的任何指针，可能是伪代码，还是方法定义？
我很熟悉Java，所以我在java下面标记了这个问题。
对于实例，这个链表有一个循环
0--->1---->2---->3---->4---->5---->6 ▲ | | ▼ 11<—-22<—-12<—-9<—-8 这个问题有两个部分：
- 检测列表中是否有循环
- 确定循环的开始
一旦知道循环开始的位置，就很容易识别列表中的最后一个元素，因为它是循环开始之后列表中的元素，最后指向循环的开始。 然后把这个元素的下一个指针/引用设置为null来修正循环链接列表（不是循环链接列表，这是最后一个元素指向第一个元素的地方 – 这将是循环列表的特定实例）。
-
Floyd的周期检测algorithm，也被称为乌龟和兔子algorithm，因为它涉及使用两个以不同速度移动的指针/参考，是检测周期的一种方法。 如果有一个循环，两个指针（比如说
p1和p2）最终会在有限的步数之后指向同一个元素。 有趣的是，可以certificate，它们相遇的元素与循环开始处的距离相同（继续以相同的前向方向遍历列表），因为循环的开始是到列表的头部 。 也就是说，如果列表的线性部分有k元素，那么这两个指针将会在从循环开始的mk点或k元素到循环的“结束”的点mk处的长度为m的循环内相遇（当然，这是一个循环，所以它没有'结束' – 这只是'开始'再次）。 这给了我们一个find循环开始的方法： -
一旦检测到一个周期，让
p2保持指向上述步骤的循环终止的元素，但重置p1，使其指向列表的头部。 现在，每次移动每个指针一个元素。 由于p2在循环内部开始，它将继续循环。 在k步之后（等于从列表头开始的循环的距离），p1和p2将再次相遇。 这会给你一个循环开始的参考。 -
现在很容易将
p1（或p2）设置为指向启动循环的元素并遍历循环，直到p1结束指向开始元素。 此时，p1引用“last”元素列表，并且下一个指针可以设置为null。
下面是一些快速和肮脏的Java代码，假设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第一次见面时周期中的位置是多less？
定义循环中的第一个节点是位置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-does-Floyds-cycle-finding-algorithm-work
- 说明如何查找循环链表中的循环开始节点工作？
- 在链表中检测循环开始的certificate
- Hristo在这个页面上对这个问题的回答也引用了一本采访书的解释
解决scheme1 – 由事业杯和“破解编码面试”书 ：
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; }
这本解决scheme的解释是直接从书中：
如果我们移动两个指针，一个是速度为1，另一个是速度为2的指针，如果链表有一个循环，它们将结束会议。 为什么？ 想想两辆车在赛道上行驶; 越快的赛车总是会越慢！
这里棘手的部分是find循环的开始。 想象一下，作为一个比喻，两个人在一个赛道上跑，一个跑的速度是另一个的两倍。 如果他们在同一个地方出发，他们下次什么时候见面？ 接下来他们将在下一圈开始时相遇。
现在，让我们假设快步跑者在第n圈有一个k米的开局。 他们下次什么时候见面？ 他们将在下一圈开始前达到k米。 （为什么？快跑者会做出k + 2（n-k）个步骤，包括它的开始，慢跑者会做n-k个步骤。
现在，回到这个问题，当快速跑者（n2）和慢跑者（n1）在我们的循环链表中移动时，当n1进入时，n2将在循环中有一个开始。 具体而言，它将具有k的头部起始点，其中k是循环之前的节点的数量。 由于n2具有k个节点的起点，所以n1和n2将在循环开始之前遇到k个节点。
所以，我们现在知道以下几点：
- Head是LoopStart的k个节点（按照定义）
- MeetingPoint for n1和n2是LoopStart的k个节点（如上所示）
因此，如果我们将n1移回Head并在MeetingPoint保留n2，并以相同的速度移动它们，它们将在LoopStart
解决scheme2 – 我的礼貌:)
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; }
我希望这有帮助。
斯托伊奇
这个回答并不是为了争夺答案，而是在乌龟和兔子algorithm的两个节点的会议上多加一点解释。
-
两个节点最终都将进入循环。 （F）比其他（S）快，（F）最后一圈（S）。
-
如果循环的开始在列表的头部，（F）必须在列表头部回到（S）。 这只是因为（F）的速度是2X（S）的; 如果是3X，那么这是不对的。 这是因为当（S）完成半圈时（F）完成一圈，所以当（S）完成第一圈时，（F）完成了两圈 – 并且以（S）返回到循环的开始， 。
-
如果循环的开始不在列表的头部，那么在（S）进入循环时，（F）在循环中具有（k）个节点的首部开始。 因为（S）的速度一次只有一个节点，所以它会在（k）节点处从循环开始到达（F） – 如（k）在到达开始之前的更多步骤，NOT（k）开始。 如果（S）的速度不是1，速度比在（F）和（S）之间不是2：1，那么这是不正确的。
3.1。 这是一个棘手的解释。 我们可以同意，（F）将继续研究（S），直到它们最终会见（见上面的1），但为什么在（k）循环的节点开始？ 考虑下面的等式，其中M是节点的数量或环路的距离，并且k是起始（F）所具有的; 该等式表示在（S）的右侧行驶的距离方面，（F）左侧行驶的距离：
d_F（t）= 2 * d_S（t）+ k
所以当（S）进入环路并且在环路中行进了0距离时，（F）仅行进了（k）距离。 到时间d_S = M-k，d_F = 2M-k。 因为我们还必须考虑到M代表循环中单圈的总距离，因此我们也必须使用模math。任何整个M（无余数）处（F）和（S）的位置都是0。 POSITION（或差分），这离开k（或者说，-k）。
最后，（S）和（F）会在（0 – k）位置相遇，或者（k）离开循环开始的节点。
-
（k）代表起始点（F），并且（F）已经行进距离（S）从列表的头部行进的距离（S），（k）也代表距列表开始的距离，然后代表循环的开始。
这里有点晚了，所以我希望我已经有效地阐述了。 让我知道，否则我会尝试更新我的回应。
如果使用身份哈希映射（如IdentityHashMap ）是允许的，这非常容易解决。 它确实占用了更多的空间。
遍历节点列表。 对于遇到的每个节点，将其添加到标识映射。 如果节点已经存在于身份映射中，那么该列表具有循环链接，并且在该冲突之前的节点是已知的（在移动之前检查或保留“最后节点”） – 简单地将“下一个”设置为恰当的打破循环。
遵循这个简单的方法应该是一个有趣的练习：代码留给读者作为练习。
快乐的编码。
0--->1---->2---->3---->4---->5---->6 ▲ | | ▼ 11<—-22<—-12<—-9<—-8
在链表的每个节点之后插入虚拟节点，并在插入之前检查下一个节点是否为虚拟节点。 如果下一个是dummy，则在该节点的下一个位置插入null。
0-->D->1-->D->2-->D->3->D-->4->D-->5->D-->6 ▲ | / ▼ 11<—D<-22<—D<-12<—D<-9<—D<--8 Node(11)->next->next == D Node(11)->next =null
