연결된 목록에 Java주기가 있는지 확인하는 방법?

Question

다음과 같이 링크 된 목록에주기가 있는지 확인하는 구현이 있습니다. true이면 true를 반환하고 그렇지 않으면 false를 반환합니다.

코드가 정확하다고 보이지만주기가 있어도 false가 반환됩니다. 내가 뭘 놓치고 있니? 목록주기, 가 있거나 다른 사람의 끝에 도달하면 walker 한 단계 및 2 단계로 진전 runner에 의해 발전 는 결국 만날 것입니다 : 알고리즘은 참으로 정확 당신에게

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

감사 명부.

이주기 탐지 구현은 노드 값에 대한 사이클을 감지하지 않지만 노드는으로 표시됩니다. 더주기는 노드의 관점에서 여기가 없습니다 :

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;