Linked List Cycle II

Linked List Cycle II

What is this problem about?

The "Linked List Cycle II interview question" is an extension of the basic cycle detection problem. Not only do you need to determine if a cycle exists, but you must also find the exact node where the cycle begins. If no cycle exists, return null. This "Linked List Cycle II coding problem" requires a deeper mathematical understanding of the two-pointer approach.

Why is this asked in interviews?

Companies like Meta and Amazon ask this to see if a candidate can derive or remember the mathematical relationship between the meeting point and the cycle's entrance. It tests "Linked List interview pattern" proficiency and the ability to refine a "Two Pointers interview pattern" into a multi-step algorithm.

Algorithmic pattern used

The pattern is still Floyd's Tortoise and Hare, but with an extra phase.

• Phase 1: Find the meeting point of the slow and fast pointers.
• Phase 2: Once they meet, place one pointer back at the head of the list and keep the other at the meeting point. Move both pointers one step at a time. The node where they meet again is the start of the cycle. This works because of the mathematical distance relationships within a looped linked list.

Example explanation

List: 3 -> 2 -> 0 -> -4, and -4 points back to 2.

1. Phase 1: Slow and Fast meet at node '0' (as in the basic cycle problem).
2. Phase 2: Put Pointer A at the head (node 3) and Pointer B at the meeting point (node 0).
3. Step 1: Move A to 2, Move B to 2 (from 0 to -4 to 2).
4. They meet at node '2', which is the entrance to the cycle.

Common mistakes candidates make

• Off-by-one errors: Moving the pointers an extra step or stopping a step too early in Phase 2.
• Not handling the "No Cycle" case: Forgetting to return null if the fast pointer reaches the end of the list in Phase 1.
• Mathematical confusion: Being unable to explain why Phase 2 works (the distances are L1 = n*C - L2).

Interview preparation tip

Practice the derivation of the distance formula for this problem. Understanding the math behind it makes it much easier to remember and implement during a high-pressure interview.