如何检测链表中的循环？

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 prev = null;Node cur = first;while (cur != null) {
    Node next = cur.next;
    cur.next = prev;
    prev = cur;
    cur = next;}boolean hasCycle = prev == first && first != null && first.next != null;// reconstruct the listcur = prev;prev = null;while (cur != null) {
    Node next = cur.next;
    cur.next = prev;
    prev = cur;
    cur = next;}return hasCycle;

测试代码：

static void assertSameOrder(Node[] nodes) {
    for (int i = 0; i < nodes.length - 1; i++) {
        assert nodes[i].next == nodes[i + 1];
    }}public static void main(String[] args) {
    Node[] nodes = new Node[100];
    for (int i = 0; i < nodes.length; i++) {
        nodes[i] = new Node();
    }
    for (int i = 0; i < nodes.length - 1; i++) {
        nodes[i].next = nodes[i + 1];
    }
    Node first = nodes[0];
    Node max = nodes[nodes.length - 1];

    max.next = null;
    assert !hasCycle(first);
    assertSameOrder(nodes);
    max.next = first;
    assert hasCycle(first);
    assertSameOrder(nodes);
    max.next = max;
    assert hasCycle(first);
    assertSameOrder(nodes);
    max.next = nodes[50];
    assert hasCycle(first);
    assertSameOrder(nodes);}