Problem Description

Given the head of a linked list, determine the node where a cycle begins. If no cycle exists, return null. The cycle is identified when a node can be reached again by continuously following the next pointer. The solution must not modify the original linked list.

Algorithm Explanation

Floyd's Cycle Detection Algorithm, also known as the Tortoise and Hare algorithm, employs two pointers moving at different speeds. The slow pointer advances one node at a time, while the fast pointer advances two nodes per iteration. If a cycle exists, the fast pointer will eventually catch up to the slow pointer inside the cycle.

Once a meeting point is confirmed, a second phase begins: one pointer resets to the head while the other remains at the meeting position. Both pointers then move one step at a time. The node where they converge is the entry point of the cycle.

Mathematical Proof: Let the distance from head to cycle entry be a, the distance from entry to meeting point be b, and the remaining distance in the cycle be c. When the pointers meet:

• Slow pointer traveled: a + b
• Fast pointer traveled: a + b + c + b = a + 2b + c
• Since fast travels twice the distance: 2(a + b) = a + 2b + c, therefore a = c

This proves that moving one pointer from the head and one from the meeting point synchronously will result in convergence at the cycle entry.

Implementation

public class CycleDetection {

    static class Node {
        int data;
        Node next;

        Node(int val) {
            this.data = val;
        }
    }

    public static Node findCycleEntry(Node head) {
        if (head == null || head.next == null) {
            return null;
        }

        Node tortoise = head;
        Node hare = head;

        // Phase 1: Detect if a cycle exists
        while (hare != null && hare.next != null) {
            tortoise = tortoise.next;
            hare = hare.next.next;

            if (tortoise == hare) {
                // Phase 2: Locate the cycle entry point
                Node seeker = head;
                Node keeper = tortoise;

                while (seeker != keeper) {
                    seeker = seeker.next;
                    keeper = keeper.next;
                }

                return seeker;
            }
        }

        return null;
    }

    public static void main(String[] args) {
        Node start = new Node(3);
        start.next = new Node(2);
        start.next.next = new Node(0);
        start.next.next.next = new Node(-4);
        start.next.next.next.next = start.next;

        Node result = findCycleEntry(start);
        if (result != null) {
            System.out.println("Cycle entry node value: " + result.data);
        } else {
            System.out.println("No cycle detected");
        }
    }
}

Complexity Analysis

Time Complexity: O(n) - Each node is visited at most twice during both phases.

Space Complexity: O(1) - Only two pointers are used regardless of input size.