Linked List Cycle

Given the head of a linked list, determine if the list has a cycle.

Function signature

func HasCycle(head *ListNode) bool

Inputs / outputs

• head: pointer to the first node.
• Return: true if there is a cycle.

Example

1 -> 2 -> 3 -> 4
     ^         |
     |_________|
Output: true

Constraints

• 0 <= number of nodes <= 100_000

Core idea (near-solution)

Use Floyd's Tortoise and Hare:

• slow moves 1 step.
• fast moves 2 steps.

Invariant: if a cycle exists, fast will eventually meet slow.

Algorithm (step-by-step)

1. Initialize slow = head, fast = head.
2. While fast and fast.Next are not nil:
   • Move slow one step.
   • Move fast two steps.
   • If they meet, return true.
3. Return false.

Correctness sketch

• Invariant: if a cycle exists, fast will eventually meet slow.
• 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
     ^         |
     |_________|
Output: true

Walk:
- slow=1, fast=2
- slow=2, fast=4
- slow=3, fast=3 -> meet -> cycle exists

Pitfalls to avoid

• Not checking fast.Next before advancing.

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.