Start of LinkedList Cycle (Finding the Loop Entry Node)

• Phase 1 (detection) – slow moves one node, fast moves two nodes per step; if they meet, a cycle exists.
• Phase 2 (entry finding) – reset one pointer to the head, advance both at one step; they meet at the cycle's entry.
• Distance proof – fast traveled 2x slow's distance; algebra shows head-to-entry distance equals meeting-point-to-entry distance around the loop.
• No cycle – if fast reaches null, return null.
• Complexity – O(n) time, O(1) space.

What is the problem?

Given a linked list that may contain a cycle, return the node where the cycle begins. If there is no cycle, return null. The solution must use O(1) extra space, so storing visited nodes in a HashSet is not allowed.

How does Phase 1 (cycle detection) work?

Use Floyd's algorithm: a slow pointer moves one node per step and a fast pointer moves two nodes per step. If a cycle exists, they will eventually meet inside the cycle. If no cycle exists, the fast pointer reaches null.

ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow == fast) break; // met inside the cycle
}
if (fast == null || fast.next == null) return null; // no cycle

How does Phase 2 (entry finding) work?

Reset one pointer to the head and keep the other at the meeting point. Advance both one step at a time. They meet at the cycle's entry.

package com.bank.service;

public class CycleDetector {

    static class ListNode {
        int val;
        ListNode next;
        ListNode(int val) { this.val = val; }
    }

    public static ListNode findCycleStart(ListNode head) {
        if (head == null) return null;

        // Phase 1: detect cycle
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                // Phase 2: find entry
                ListNode entry = head;
                while (entry != slow) {
                    entry = entry.next;
                    slow = slow.next;
                }
                return entry;
            }
        }
        return null; // no cycle
    }

    public static void main(String[] args) {
        // T1 -> T2 -> T3 -> T4 -> T5 -> T3 (cycle at T3)
        ListNode t1 = new ListNode(1);
        ListNode t2 = new ListNode(2);
        ListNode t3 = new ListNode(3);
        ListNode t4 = new ListNode(4);
        ListNode t5 = new ListNode(5);
        t1.next = t2; t2.next = t3; t3.next = t4; t4.next = t5; t5.next = t3;

        ListNode start = findCycleStart(t1);
        System.out.println("Cycle starts at node: " + start.val);
    }
}

Cycle starts at node: 3

Why does Phase 2 work?

• Let the distance from head to cycle entry be d, and the distance from cycle entry to meeting point be k, and the cycle length be C. When slow and fast meet:
• Slow traveled: d + k
• Fast traveled: d + k + nC (for some integer n)
• Since fast travels 2x slow: d + k + nC = 2(d + k), so nC = d + k, meaning d = nC - k

This means walking d steps from the meeting point brings you back to the entry (because nC - k steps around the loop lands at the entry). Walking d steps from the head also reaches the entry. So both pointers meet at the entry.

What are edge cases?

• No cycle: fast reaches null, return null.
• Cycle at the head: the entry is the head itself.
• Single node pointing to itself: slow and fast meet at head, phase 2 immediately returns head.
• Long tail before a small cycle.

What are common mistakes?

// Wrong: using double speed in phase 2
ListNode entry = head;
while (entry != slow) {
    entry = entry.next;
    slow = slow.next.next; // WRONG! Must be single step
}

// Correct: both single step in phase 2
while (entry != slow) {
    entry = entry.next;
    slow = slow.next; // single step
}

How is this different from just detecting a cycle?

| Feature | Cycle Detection | Cycle Entry Finding |
|---|---|---|
| Phases | 1 phase | 2 phases |
| Returns | boolean (cycle exists?) | the entry node |
| Phase 2 | not needed | reset to head, equal speed |
| Use case | is there corruption? | where is the corruption? |

What should a senior engineer know?

A senior engineer understands that the correctness of phase 2 depends entirely on the 2:1 speed ratio in phase 1, which creates the distance equation. Changing the speed ratio (e.g., 3:1) would require a different phase 2 algorithm.

In a banking repair tool at National Bank of India, the integrity checker detected a loop in a transaction chain, and the repair tool needed the exact record where the loop started to fix the corrupted pointer. Using Floyd's extended algorithm located the entry with only pointer operations, no extra memory.

What are common interview follow-up questions?

• How would you find the length of the cycle?
• Can you detect and find the entry in one pass without two separate phases?
• What if the list has multiple cycles (not possible in a singly linked list, but why?)?