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

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

每个节点都指向下一个节点,除了最后一个节点,它的next为空。假设有一种可能性,列表可以包含一个循环-即最后的节点,而不是有一个空值,有一个引用到列表中它之前的一个节点。

最好的写作方式是什么

boolean hasLoop(Node first)

如果给定的节点是带有循环的列表的第一个,则返回true,否则返回false ?你怎么能写出一个常数的空间和合理的时间呢?

下面是一个带有循环的列表的图片:


当前回答

 // To detect whether a circular loop exists in a linked list
public boolean findCircularLoop() {
    Node slower, faster;
    slower = head;
    faster = head.next; // start faster one node ahead
    while (true) {

        // if the faster pointer encounters a NULL element
        if (faster == null || faster.next == null)
            return false;
        // if faster pointer ever equals slower or faster's next
        // pointer is ever equal to slower then it's a circular list
        else if (slower == faster || slower == faster.next)
            return true;
        else {
            // advance the pointers
            slower = slower.next;
            faster = faster.next.next;
        }
    }
}

其他回答

用户unicornaddict上面有一个很好的算法,但不幸的是,它包含一个错误,用于奇数长度>= 3的非循环列表。问题是,快的可能会在列表结束之前“卡住”,慢的会赶上它,然后就会(错误地)检测到循环。

这是修正后的算法。

static 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 = null;
        else
            fast = fast.next.next; // 2 hops.

        if(fast == null) // if fast hits null..no loop.
            return false;

        if(slow == fast) // if the two ever meet...we must have a loop.
            return true;
    }
}
public boolean isCircular() {

    if (head == null)
        return false;

    Node temp1 = head;
    Node temp2 = head;

    try {
        while (temp2.next != null) {

            temp2 = temp2.next.next.next;
            temp1 = temp1.next;

            if (temp1 == temp2 || temp1 == temp2.next) 
                return true;    

        }
    } catch (NullPointerException ex) {
        return false;

    }

    return false;

}

我不确定这个答案是否适用于Java,但我仍然认为它属于这里:

当我们在现代体系结构中使用指针时,我们可以期望它们是CPU字对齐的。对于64位体系结构,这意味着指针的前3位始终为零。这让我们可以使用这个内存来标记我们已经见过的指针,通过对它们的第一个比特写入1。

如果我们遇到一个指针,它的第一个位已经写了1,那么我们已经成功地找到了一个循环,之后我们需要再次遍历结构,并将这些位屏蔽掉。完成了!

这种方法被称为指针标记,它在低级编程中被过度使用,例如Haskell在一些优化中使用它。

乌龟和兔子的另一种解决方案,不太好,因为我暂时改变了列表:

这个想法是遍历列表,并在执行过程中反转它。然后,当你第一次到达一个已经被访问过的节点时,它的next指针将指向“向后”,导致迭代再次朝第一个方向进行,并在那里终止。

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);
}

我看不出有任何方法可以让这花费固定的时间或空间,两者都会随着列表的大小而增加。

我将使用IdentityHashMap(假设还没有IdentityHashSet)并将每个节点存储到映射中。在存储节点之前,您可以对其调用containsKey。如果节点已经存在,则有一个周期。

ItentityHashMap使用==而不是.equals,这样你就可以检查对象在内存中的位置,而不是它是否具有相同的内容。