Detect Cycle in Linked List

Problem Statement

Given the head of a linked list, determine if the list has a cycle in it. A cycle exists if a node’s next pointer points back to a previous node.

Example: Input: 3 → 2 → 0 → -4 (with -4.next = node at index 1), Output: true

Approach 1: Hash Set

Explanation: Store visited nodes in a set. If a node repeats, cycle exists.

Time Complexity: O(n)

Space Complexity: O(n)

visited = set()
while head != NULL:
    if head in visited:
        return true
    visited.add(head)
    head = head.next
return false

Approach 2: Floyd’s Cycle Detection

Explanation: Use two pointers (slow and fast). If they meet, cycle exists.

Time Complexity: O(n)

Space Complexity: O(1)

slow = head
fast = head
while fast != NULL and fast.next != NULL:
    slow = slow.next
    fast = fast.next.next
    if slow == fast:
        return true
return false

Why the Slow and Fast Pointers Must Meet (Proof — Simple)

Goal: Show that if a linked list has a cycle then the “slow” (1 step) and “fast” (2 steps) pointers must meet.

Assumptions

The list contains a cycle.
The cycle starts after μ nodes from the head.
The cycle length (number of nodes in loop) = k.
Slow moves 1 step per iteration; fast moves 2 steps per iteration.

Positions after t steps

After t steps from the head:

Slow has moved t nodes → position = t.
Fast has moved 2t nodes → position = 2t.

Once both pointers have entered the cycle (i.e., for t ≥ μ), only positions modulo k matter:

slow position = (t − μ) mod k
fast position = (2t − μ) mod k

Condition for meeting

They meet when their positions inside the loop are equal:

(2t − μ) mod k = (t − μ) mod k

Simplifying:

2t − μ ≡ t − μ (mod k)
⇒ t ≡ 0 (mod k)

That means t must be a multiple of k. Therefore, within at most k steps after the slow pointer enters the cycle, the two pointers will be at the same node (they meet).

Intuition / Gap argument (alternate, quick view)

After slow enters the cycle, the fast pointer is somewhere inside the loop. Each iteration the fast pointer advances exactly one node further than slow (2 − 1 = 1). So their gap (distance around the loop) decreases by 1 modulo k every step. The gap values cycle through {0,1,...,k−1}, so within at most k steps the gap becomes 0 — they meet.

Conclusion

If the linked list contains a cycle, the slow and fast pointers will definitely meet inside the loop, and this will occur within at most k steps after slow enters the cycle. If there is no cycle, fast reaches NULL and they never meet.

Summary:
- If cycle exists → slow & fast meet inside loop (within ≤ k steps after slow enters).
- If no cycle → fast becomes NULL → no meeting.