Detecting Cycles in a Linked List with Fast and Slow Pointers (Java)

Overview

The article describes a classic algorithm for detecting a cycle in a singly linked list and locating the entry node of the cycle using the fast‑slow (tortoise‑hare) pointer method.

Detecting a Cycle

First, two pointers start at the head: slow moves one step each iteration, while fast moves two steps. If the list has no cycle, fast will reach the end ( null) and the algorithm returns null. If the pointers meet, a cycle exists.

while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow == fast) {
        // cycle detected
        break;
    }
}
if (fast == null || fast.next == null) {
    return null; // no cycle
}

Finding the Entry Point

Assume the distance from the head to the cycle entry is a, the cycle length is k, and the two pointers meet after the slow pointer has traveled a + n·k + (k‑x) steps, where x is the distance from the meeting point to the entry.

The fast pointer has traveled a + m·k + (k‑x) steps. Because the fast pointer moves twice as fast, we have: a + m·k + (k - x) = 2 * (a + n·k + (k - x)) Simplifying yields: a = (m - 2n - 1)·k + x This shows that a equals an integer multiple of the cycle length k plus x. Therefore, if we reset one pointer to the head and move both pointers one step at a time, they will meet exactly at the cycle entry after x additional steps.

Complete Java Implementation

package com.javaedge;

/**
 * Detect cycle in a singly linked list and return the entry node.
 */
public class DetectCycle {
    static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        boolean isCircled = false;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                isCircled = true;
                break;
            }
        }
        if (!isCircled) {
            // no cycle
            return null;
        }
        // reset slow to head and move both one step at a time
        slow = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow; // entry node of the cycle
    }
}

Illustration