如何检测链表中的循环？

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

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

每个节点指向下一个节点，除了最后一个节点，下一个节点为空。 假设列表可能包含一个循环 - 也就是说，最终的节点（而不是一个空）会引用列表中的节点之前的节点。

什么是最好的写作方式

boolean hasLoop(Node first)

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

下面是一个循环列表的图片：

---

你可以利用弗洛伊德的循环寻找算法 ，也被称为乌龟和兔子算法。

这个想法是有两个引用列表并以不同的速度移动它们。 向前移动1节点，另一个移动2节点。

如果链表有一个循环，他们一定会见面。

否则两个引用（或其next ）中的任何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;
    }
}

---

下面是Fast / Slow解决方案的改进，它可以正确处理奇数长度的列表并提高清晰度。

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
}

---

海龟和兔子的另一种解决方案，就像我暂时改变列表一样，不太好：

这个想法是走在名单上，并在你走后反转。 然后，当你第一次到达一个已经被访问过的节点时，它的下一个指针将指向“向后”，导致迭代继续朝着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 list
cur = 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);
}

链接地址: http://www.djcxy.com/p/39681.html

上一篇: How to detect a loop in a linked list?

下一篇: How to find list of possible words from a letter matrix [Boggle Solver]