Как проверить, имеет ли связанный список цикл в 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;