Linked List Cycle II

Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return nil.

Function signature

func DetectCycle(head *ListNode) *ListNode

Inputs / outputs

• head: pointer to the first node.
• Return: the node where the cycle starts, or nil if no cycle.

Example

1 -> 2 -> 3 -> 4 -> 5
          ^         |
          |_________|
Cycle starts at node with value 3.

Constraints

• 0 <= number of nodes <= 100_000

Core idea (near-solution)

Use Floyd's cycle detection to find a meeting point. Then move one pointer to head and advance both one step at a time; they meet at the cycle start.

Invariant: the distance from head to cycle start equals the distance from meeting point to cycle start along the cycle.

Algorithm (step-by-step)

1. Run fast/slow pointers to detect a cycle.
2. If no cycle, return nil.
3. Reset one pointer to head.
4. Move both pointers one step at a time until they meet; return that node.

Correctness sketch

• Invariant: the distance from head to cycle start equals the distance from meeting point to cycle start along the cycle.
• If a cycle exists, fast gains one step per iteration and must meet slow.
• If no cycle exists, fast reaches nil, proving the list is acyclic.
• (For entry detection) resetting one pointer to head makes both pointers meet at the entry.

Trace (hand walkthrough)

Example input:
1 -> 2 -> 3 -> 4 -> 5
          ^         |
          |_________|
Cycle starts at node with value 3.

Walk:
- detect: slow=1, fast=1 -> step to slow=2 fast=3 -> slow=3 fast=5 -> slow=4 fast=4 meet
- reset p1=head(1), p2=4: step -> p1=2 p2=5; step -> p1=3 p2=3
- cycle start at node value 3

Pitfalls to avoid

• Returning the meeting node instead of the cycle entry.

Complexity

• Time: O(n)
• Extra space: O(1)

Implementation notes (Go)

• Guard the loop with fast != nil && fast.Next != nil.
• Compare node pointers, not values.