如何检测链表中的循环？

Question

如何检测链表中的循环？

假设您在Java中有一个链表结构。它由节点组成：

class Node {
    Node next;
    // some user data}

每个节点都指向下一个节点，最后一个节点除外。假设列表有可能包含一个循环 - 即最终的节点，而不是具有空值，具有对列表中之前的节点之一的引用。

什么是最好的写作方式

boolean hasLoop(Node first)

true如果给定的Node是带循环的列表的第一个，它将返回，false否则？你怎么写，这需要一个恒定的空间和合理的时间？

Answer 1

您可以使用Floyd的循环寻找算法，也称为乌龟和野兔算法。我们的想法是对列表进行两次引用，并以不同的速度移动它们。按1节点向前移动一个，按节点向前移动另一个2。如果链表有一个循环，他们肯定会遇到。否则两个引用（或它们next）中的任何一个都将成为null。实现该算法的Java函数：boolean hasLoop(Node first) {     if(first == null) // list does not exist..so no loop either         return false;     Node slow, fast; // create two references.     slow = fast = first; // make both refer to the start of the list     while(true) {         slow = slow.next;          // 1 hop         if(fast.next != null)             fast = fast.next.next; // 2 hops         else             return false;          // next node null => no loop         if(slow == null || fast == null) // if either hits null..no loop             return false;         if(slow == fast) // if the two ever meet...we must have a loop             return true;     }}

Answer 2

以下是快速/慢速解决方案的改进，可正确处理奇数长度列表并提高清晰度。boolean hasLoop(Node first) {     Node slow = first;     Node fast = first;     while(fast != null && fast.next != null) {         slow = slow.next;          // 1 hop         fast = fast.next.next;     // 2 hops          if(slow == fast)  // fast caught up to slow, so there is a loop             return true;     }     return false;  // fast reached null, so the list terminates}

Answer 3

对于Turtle和Rabbit的替代解决方案，并不像我暂时更改列表那样好：我们的想法是走在列表中，并在您前进时将其反转。然后，当您第一次到达已经访问过的节点时，其下一个指针将指向“向后”，从而导致迭代first再次继续，在此处终止。Node&nbsp;prev&nbsp;=&nbsp;null;Node&nbsp;cur&nbsp;=&nbsp;first;while&nbsp;(cur&nbsp;!=&nbsp;null)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;next&nbsp;=&nbsp;cur.next; &nbsp;&nbsp;&nbsp;&nbsp;cur.next&nbsp;=&nbsp;prev; &nbsp;&nbsp;&nbsp;&nbsp;prev&nbsp;=&nbsp;cur; &nbsp;&nbsp;&nbsp;&nbsp;cur&nbsp;=&nbsp;next;}boolean&nbsp;hasCycle&nbsp;=&nbsp;prev&nbsp;==&nbsp;first&nbsp;&&&nbsp;first&nbsp;!=&nbsp;null&nbsp;&&&nbsp;first.next&nbsp;!=&nbsp;null;//&nbsp;reconstruct&nbsp;the&nbsp;listcur&nbsp;=&nbsp;prev;prev&nbsp;=&nbsp;null;while&nbsp;(cur&nbsp;!=&nbsp;null)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;next&nbsp;=&nbsp;cur.next; &nbsp;&nbsp;&nbsp;&nbsp;cur.next&nbsp;=&nbsp;prev; &nbsp;&nbsp;&nbsp;&nbsp;prev&nbsp;=&nbsp;cur; &nbsp;&nbsp;&nbsp;&nbsp;cur&nbsp;=&nbsp;next;}return&nbsp;hasCycle;测试代码：static&nbsp;void&nbsp;assertSameOrder(Node[]&nbsp;nodes)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(int&nbsp;i&nbsp;=&nbsp;0;&nbsp;i&nbsp;<&nbsp;nodes.length&nbsp;-&nbsp;1;&nbsp;i++)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;assert&nbsp;nodes[i].next&nbsp;==&nbsp;nodes[i&nbsp;+&nbsp;1]; &nbsp;&nbsp;&nbsp;&nbsp;}}public&nbsp;static&nbsp;void&nbsp;main(String[]&nbsp;args)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;Node[]&nbsp;nodes&nbsp;=&nbsp;new&nbsp;Node[100]; &nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(int&nbsp;i&nbsp;=&nbsp;0;&nbsp;i&nbsp;<&nbsp;nodes.length;&nbsp;i++)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;nodes[i]&nbsp;=&nbsp;new&nbsp;Node(); &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(int&nbsp;i&nbsp;=&nbsp;0;&nbsp;i&nbsp;<&nbsp;nodes.length&nbsp;-&nbsp;1;&nbsp;i++)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;nodes[i].next&nbsp;=&nbsp;nodes[i&nbsp;+&nbsp;1]; &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;first&nbsp;=&nbsp;nodes[0]; &nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;max&nbsp;=&nbsp;nodes[nodes.length&nbsp;-&nbsp;1]; &nbsp;&nbsp;&nbsp;&nbsp;max.next&nbsp;=&nbsp;null; &nbsp;&nbsp;&nbsp;&nbsp;assert&nbsp;!hasCycle(first); &nbsp;&nbsp;&nbsp;&nbsp;assertSameOrder(nodes); &nbsp;&nbsp;&nbsp;&nbsp;max.next&nbsp;=&nbsp;first; &nbsp;&nbsp;&nbsp;&nbsp;assert&nbsp;hasCycle(first); &nbsp;&nbsp;&nbsp;&nbsp;assertSameOrder(nodes); &nbsp;&nbsp;&nbsp;&nbsp;max.next&nbsp;=&nbsp;max; &nbsp;&nbsp;&nbsp;&nbsp;assert&nbsp;hasCycle(first); &nbsp;&nbsp;&nbsp;&nbsp;assertSameOrder(nodes); &nbsp;&nbsp;&nbsp;&nbsp;max.next&nbsp;=&nbsp;nodes[50]; &nbsp;&nbsp;&nbsp;&nbsp;assert&nbsp;hasCycle(first); &nbsp;&nbsp;&nbsp;&nbsp;assertSameOrder(nodes);}