Tortoise and Hare

To catch someone on a circular track, you don't run at the same speed. You run faster. Eventually, you're guaranteed to meet.

How can you detect a cycle in a sequence? Try this problem before reading on.

Problem: Linked List Cycle: (LeetCode Link) : Given a linked list, determine if it has a cycle in it. 💡 HintUse two pointers moving at different speeds.

One approach to solve the above problem is to store every node you visit in a hash set, but do we really need to use extra space? The most optimal solution here is to use the tortoise and hare algorithm (fast and slow pointers).

How It Works

The general algorithm is as follows:

1. Initialize Pointers: Start both slow and fast pointers at the beginning of the list.
2. Iterate with Different Speeds: In a loop, move slow by one step (slow = slow.next) and fast by two steps (fast = fast.next.next).
3. Safely Handle Edge Cases: Ensure that the fast pointer does not go out of bounds, especially in linked lists.
4. Identify End State:
   • If the fast pointer meets the slow pointer, a cycle exists.
   • If fast pointer reaches the end of the list, slow pointer is at or near the middle of the list.

Walkthrough: Solving "Linked List Cycle"

def hasCycle(head):
    if not head or not head.next:
        return False

    slow = head
    fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

        if slow == fast:
            return True

    return False

public boolean hasCycle(ListNode head) {
    if (head == null || head.next == null) return false;

    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;
}

bool hasCycle(ListNode *head) {
    if (head == nullptr || head->next == nullptr) return false;

    ListNode *slow = head;
    ListNode *fast = head;

    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;

        if (slow == fast) {
            return true;
        }
    }

    return false;
}

Complexity Analysis

• Time Complexity: $O(n)$ - Although the fast pointer moves faster, the total number of steps is proportional to the number of nodes in the list.
• Space Complexity: $O(1)$ - Only two pointers are used, regardless of the size of the list.

Variation: Read and Write Pointers

Another variation of this pattern is the Read-Write Pointer. This is often used to modify an array in-place.

• How it Works: One pointer (read) iterates through the array to examine every element. A second pointer (write) lags behind, only moving when it needs to place a valid element. This ensures that you don't overwrite data before you've had a chance to read it.
• Practice Problem: Remove Duplicates from Sorted Array (LeetCode Link). 💡 HintThe write pointer only advances and writes a new value when the read pointer finds an element that is different from the one before it.

More Problems & Variations

1. Middle of the Linked List: Find the middle node of a linked list 💡 HintWhen the fast pointer reaches the end, where will the slow pointer be?
2. Remove Nth Node From End of List: Remove the nth node from the end of a linked list in one pass 💡 HintThis is a minor variation. Fast pointer should always be n steps ahead of slow pointer.
3. Move Zeroes: Move all zeroes to the end of the array while maintaining the order of non-zero elements 💡 HintUse a read pointer to traverse and a write pointer to place non-zero elements.
4. Linked List Cycle II: You know how to detect cycles, but can you find out where it begins? 💡 HintThis is a clever one, if you start a new pointer at head, it will meet the slow pointer at the cycle start.