如何检测链表中的循环?

问题:

说你在Java中有一个链表结构。它由节点组成:

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

并且每个节点指向下一个节点,但最后一个节点除外,其后一个节点为null。假设列表可能包含一个循环,即最终的节点,而不是一个空值,它具有引用到它之前的列表中的一个节点。
什么是最好的写作方式?

boolean hasLoop(Node first)

如果给定的节点是具有循环的列表中的第一个,则返回true,否则为false?你怎么写,这样就需要不断的空间和合理的时间呢?
以下是一个循环列表的图片:
 alt text

回答:

您可以使用Floyd’s cycle-finding algorithm,也称为tortoise and hare algorithm

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

  • 如果链表有一个循环
    definitely见面。
  • 否则
    两个引用(或他们的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;
    }
}

 
 
Code问答: http://codewenda.com/topics/python/
Stackoverflow: How to detect a loop in a linked list?

*转载请注明本文链接以及stackoverflow的英文链接

发表评论

电子邮件地址不会被公开。 必填项已用*标注

6 + 4 =