如何檢查鏈表是否在Java中有循環？

Question

我有以下實現，檢查鏈表是否有循環。如果是，則返回true，否則返回false。

看起來代碼是正確的，但即使它有一個循環它仍然返回false。我錯過了什麼？謝謝

import java.util.*; 

class ListNode { 
    int val; 
    ListNode next; 

    ListNode(int x) { 
     val = x; 
     next = null; 
    } 
} 

class LinkedListCycle { 
    boolean hasCycle(ListNode head) { 
     if(head == null) { 
      return false; 
     } 

     ListNode walker = head; 
     ListNode runner = head; 

     while(runner.next!=null && runner.next.next!=null) { 
      walker = walker.next; 
      runner = runner.next.next; 
      if(walker==runner) return true; 
     } 

     return false; 
    } 

    public static void main(String args[]) { 
     LinkedListCycle llc = new LinkedListCycle(); 

     ListNode ln = new ListNode(1); 
     ln.next = new ListNode(2); 
     ln.next.next = new ListNode(3); 
     ln.next.next.next = new ListNode(4); 
     ln.next.next.next.next = new ListNode(2); 
     ln.next.next.next.next.next = new ListNode(1); 

     System.out.println(llc.hasCycle(ln)); 
    } 
} 

Answer 1

的算法的確是正確的： 的walker推進的一個步驟和runner通過2步推進， 終將會如果列表中有一個週期， 或其他事項達成的結束滿足名單。

該循環檢測實現不檢測週期，根據節點值，但是根據節點。 沒有循環這裏節點方面：

ListNode ln = new ListNode(1); 
ln.next = new ListNode(2); 
ln.next.next = new ListNode(3); 
ln.next.next.next = new ListNode(4); 
ln.next.next.next.next = new ListNode(2); 
ln.next.next.next.next.next = new ListNode(1); 

會有，如果這樣寫的：

ListNode ln = new ListNode(1); 
ln.next = new ListNode(2); 
ln.next.next = new ListNode(3); 
ln.next.next.next = new ListNode(4); 
ln.next.next.next.next = ln.next;