How to check if a linked list has a cycle in Java?

Question

I have the following implementation that checks to see if a linked list has a cycle. If it does, it would return true, and false if it doesn't.

It seems like the code is correct, but it is returning false even if it does have a cycle. What am I missing? Thank you

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

• nail fei: you'd better post the case, when there exist cycle and it return false.

Answer 1

The algorithm is indeed correct: the walker advancing by one step and the runner advancing by 2 steps, will eventually will meet if the list has a cycle, or else reach the end of the list.

This cycle detection implementation doesn't detect cycle in terms of node values, but in terms of nodes. There is no cycle here in terms of nodes:

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

There would be, if written like this:

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;

• Jo Ko: Thank you so much for the clarification. So are the node values are necessary in fact? And how is it that the walker will eventually meet the runner?
• janos: The node values are data. The point of data structures is to contain some data, isn't it. In this exercise they may seem pointless, well that's just how exercises are. The walker and the runner meet, just like if you run in circles with a faster runner, he will eventually overtake you, again, and again, and again.