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

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;