リンクされたリストに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

ありがとう： 一歩と2つの段階で進めrunnerによって進めwalker、 は最終的にリストがサイクルを持っている場合 、会うか、他の終わりに達するだろうリスト。

このサイクル検出の実装では、ノード値の点でサイクルを検出するが、ノードの点ではありません。 ここにはサイクルがノードの面ではありません。

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;