The O(n) Club: Linked List Cycle II — Get Over Yourself and Find the Actual Cycle Start

The O(n) Club: Linked List Cycle II — Get Over Yourself and Find the Actual Cycle Start

⚡ TL;DR

You’re over here detecting cycles like it’s a carnival game, but can you actually put your finger on where the loop begins? Sure, you can brute-force this with a HashSet and nuke your memory budget. But you want to be clever — right?

// Shameless brute-force for the desperate
Set<ListNode> seen = new HashSet<>();
while (head != null) {
    if (seen.contains(head)) return head;
    seen.add(head);
    head = head.next;
}
return null;

🧠 How Devs Usually Mess This Up

Here’s developer folklore: “Just return the spot where slow and fast pointers meet, that’s the start!” Nope. That’s just the cycle’s social gathering, not its front door. Or there’s always that one dev who throws a HashSet at it, as if RAM is free. (Hint: in interviews, it’s not.)

🔍 What’s Actually Going On

Picture a tortoise and a hare running on a bizarre racetrack with a sneaky loop. The hare inevitably laps the tortoise, but their accidental rendezvous will never be at the exact start of the loop. Here’s the power move: reset tortoise to head, then let both joggers advance one node at a time. When they next shake hands? Bingo — you’ve found the very beginning of the cycle. It’s not luck, it’s math. Want the nitty-gritty? The distance from head to the cycle’s entry is exactly the same as from crash-site to entry, but following the loop. Wild, right?

🛠️ PseudoCode

• Initialize two pointers (slow, fast) at head.
• Move slow by 1 step, fast by 2. If they meet — yes, there’s a cycle.
• Reset slow to head. Now advance both slow and fast one step at a time.
• Where they next meet is the cycle’s official start node. (If anyone hits null, abandon all hope — no cycle.)

💻 The Code

// Singly-linked list node
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; next = null; }
}
 public ListNode detectCycle(ListNode head) {
    ListNode slow = head, fast = head;
    // Phase 1: Detect cycle
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            // Phase 2: Find start
            slow = head;
            while (slow != fast) {
                slow = slow.next;
                fast = fast.next;
            }
            return slow;
        }
    }
    return null;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Stop returning the first meeting node — it isn’t the start. Reset or be reset.
• Test the single node cycle (where a node points to itself). Works. No badge, but you passed.
• HashSet is a copout: O(n) extra space when O(1) will do. Go minimalist; interviewers love that.
• Time? O(n). Space? Two pointers and a dream.

🧠 Interviewer Brain-Tattoo

If you can’t elegantly sync two pointers at the start of the cycle, you’re just chasing your own tail — which, ironically, is exactly what this problem is about.