7.9 Linked List Cycle

7.9.1 Problem Metadata

7.9.2 Description

Detect whether a linked list has a cycle.

7.9.3 Solution - Floyd’s Cycle Detection

7.9.3.1 Walkthrough

Floyd’s algorithm uses two pointers moving at different speeds. The slow pointer advances one node at a time while the fast pointer advances two nodes. If there’s a cycle, the fast pointer will eventually catch up to the slow pointer from behind (they will meet). If there’s no cycle, the fast pointer will reach the end (null).

Why they must meet if a cycle exists: Once both pointers enter the cycle, the fast pointer closes the gap by 1 node per iteration. Since the gap decreases by exactly 1 each step, they will eventually meet.

7.9.3.2 Analysis

  • Time Complexity: O(n) - In the worst case, we traverse the list twice (once to enter the cycle, once to meet)
  • Space Complexity: O(1) - Only two pointers used

7.9.3.3 Implementation Steps

  1. Initialize both slow and fast pointers to head.
  2. Move slow by one step and fast by two steps in each iteration.
  3. If slow == fast at any point, a cycle exists.
  4. If fast or fast.next becomes null, no cycle exists.

7.9.3.4 Code - Java

public boolean hasCycle(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            return true;
        }
    }
    return false;
}