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

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

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

最好的写作方式是什么

boolean hasLoop(Node first)

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

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


当前回答

你也可以使用上述答案中所建议的弗洛伊德乌龟算法。

该算法可以检查单链表是否具有闭合循环。 这可以通过迭代带有两个移动速度不同的指针的列表来实现。通过这种方式,如果存在一个循环,两个指针将在未来的某个时间点相遇。

请随意查看我关于链表数据结构的博客文章,在那里我还包含了一个用java语言实现上述算法的代码片段。

问候,

安德烈亚斯 (@xnorcode)

其他回答

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

这个想法是遍历列表,并在执行过程中反转它。然后,当你第一次到达一个已经被访问过的节点时,它的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);
}
 // 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;
        }
    }
}

在这个上下文中,到处都有文本材料的加载。我只是想张贴一个图表表示,真正帮助我掌握概念。

当快、慢在点p相遇时,

快速行进的距离= a+b+c+b = a+2b+c

慢行距离= a+b

因为快的比慢的快2倍。 所以a+2b+c = 2(a+b)然后得到a=c。

因此,当另一个慢指针再次从头部运行到q时,同时,快速指针将从p运行到q,因此它们在q点会合。

public ListNode detectCycle(ListNode head) {
    if(head == null || head.next==null)
        return null;

    ListNode slow = head;
    ListNode fast = head;

    while (fast!=null && fast.next!=null){
        fast = fast.next.next;
        slow = slow.next;

        /*
        if the 2 pointers meet, then the 
        dist from the meeting pt to start of loop 
        equals
        dist from head to start of loop
        */
        if (fast == slow){ //loop found
            slow = head;
            while(slow != fast){
                slow = slow.next;
                fast = fast.next;
            }
            return slow;
        }            
    }
    return null;
}

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

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

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

我可能会非常晚和新的处理这个线程。但还是. .

为什么不能将节点的地址和“下一个”节点指向存储在表中

如果我们可以这样做

node present: (present node addr) (next node address)

node 1: addr1: 0x100 addr2: 0x200 ( no present node address till this point had 0x200)
node 2: addr2: 0x200 addr3: 0x300 ( no present node address till this point had 0x300)
node 3: addr3: 0x300 addr4: 0x400 ( no present node address till this point had 0x400)
node 4: addr4: 0x400 addr5: 0x500 ( no present node address till this point had 0x500)
node 5: addr5: 0x500 addr6: 0x600 ( no present node address till this point had 0x600)
node 6: addr6: 0x600 addr4: 0x400 ( ONE present node address till this point had 0x400)

这样就形成了一个循环。