Java如何检测链表中的循环？

Java如何检测链表中的循环？

想法是要有两个引用列表，并以不同的速度移动它们。一个向前移动一个

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