#141 Linked List Cycle

Problem Statement

Given head, the head of a linked list, determine if the linked list has a cycle in it. A cycle exists if some node can be reached again by continuously following the next pointer.

Intuition

If a cycle exists, a fast pointer (moving two steps at a time) will eventually lap a slow pointer (moving one step). If there's no cycle, the fast pointer reaches the end.

This is known as Floyd's cycle detection algorithm, or the tortoise and hare algorithm.

Approach

1. Initialize two pointers, slow and fast, both at head.
2. Move slow one step and fast two steps per iteration.
3. If fast or fast.next is null, return false (no cycle).
4. If slow === fast, return true (cycle detected).

Solution

function hasCycle(head: ListNode | null): boolean {
  let slow = head;
  let fast = head;

  while (fast && fast.next) {
    slow = slow!.next;
    fast = fast.next.next;
    if (slow === fast) return true;
  }

  return false;
}

Complexity Analysis