Linked List Cycle II

Problem Link

142. Linked List Cycle II – LeetCode

Problem Statement

Given the head of a singly linked list, return the node where the cycle begins.

If there is no cycle, return null.

You must not modify the list.

Examples

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: Node with value 2
Explanation: The cycle starts at the node with index 1 (value 2).

Example 2:

Input: head = [1,2], pos = 0
Output: Node with value 1

Example 3:

Input: head = [1], pos = -1
Output: null

Constraints

• The number of nodes in the list is in the range [0, 10⁴]

• -10⁵ <= Node.val <= 10⁵

• pos is the index where the tail connects; -1 means no cycle

Intuition

This is an extension of Floyd’s Cycle Detection Algorithm (Tortoise and Hare).

Once a cycle is detected using two pointers (slow, fast), we can find the start node of the cycle using a key mathematical insight based on distances.

Approach: Floyd’s Tortoise and Hare (Cycle Detection + Entry Point)

1. Use two pointers (slow and fast) to detect the cycle:

   • slow moves 1 step

   • fast moves 2 steps

   • If they meet → cycle exists

2. Reset slow to head, keep fast at meeting point.

3. Move both one step at a time; the node where they meet again is the start of the cycle.

Why It Works (Mathematical Proof)

Let:

• a = distance from head to cycle start

• b = distance from cycle start to meeting point

• c = cycle length

At meeting point:

• slow = a + b

• fast = a + b + n*c for some integer n (fast does extra cycles)

Since fast = 2 * slow,
→ 2(a + b) = a + b + n*c
→ a + b = n*c
→ a = n*c - b

So, if we move one pointer from head and one from meeting point, both moving 1 step at a time, they will meet at the start of the cycle after a steps.

Java Code

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;

        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;

            if (fast == slow) {
                // cycle detected
                slow = head;
                while (slow != fast) {
                    slow = slow.next;
                    fast = fast.next;
                }
                return slow; // start of the cycle
            }
        }

        return null; // no cycle
    }
}

Time and Space Complexity

Dry Run

Input:

List: 3 → 2 → 0 → -4
             ↑     ↓
             ← ← ←

• slow and fast meet at -4

• Reset slow to head

• Move both pointers → they meet at node 2

Output: Node with value 2

Alternate Approach

Using a HashSet<ListNode> to track visited nodes:

• Traverse the list and store visited nodes

• If a node is revisited, that’s the start of the cycle

public ListNode detectCycle(ListNode head) {
    Set<ListNode> visited = new HashSet<>();
    while (head != null) {
        if (visited.contains(head)) return head;
        visited.add(head);
        head = head.next;
    }
    return null;
}

• Time: O(n)

• Space: O(n)

Conclusion

This problem is a perfect demonstration of mathematics in pointer logic. Floyd’s algorithm efficiently detects cycles and locates their start with O(1) space, making it an essential pattern to master in linked list problems.