Fast and Slow Pointers Pattern: Detecting Cycles Efficiently

Let's explore the Fast and Slow Pointers pattern, also known as the "Hare and Tortoise" algorithm, which is used to detect cycles in linked lists and other data structures.

Fast and Slow Pointers Pattern (Hare and Tortoise)

Concept:

The Fast and Slow Pointers (also known as the "Hare and Tortoise" algorithm) is a pointer technique commonly used to solve problems that involve cyclic data structures or where you need to determine relationships between nodes in a sequence. The fast pointer moves two steps at a time, while the slow pointer moves one step at a time. If there’s a cycle, the fast pointer will eventually "lap" the slow pointer.

Example Problem:

Determine if a linked list has a cycle.

Problem Statement:

You are given a linked list. Determine if the linked list has a cycle in it (i.e., if any node is visited more than once while traversing the list).

Brute Force Approach:

A brute-force method might involve using a hash set to store visited nodes, but this uses extra memory and results in O(n) space complexity.

Optimized Fast and Slow Pointer Approach:

Using the fast and slow pointer approach, we can solve this problem efficiently with O(1) space complexity.

Java Code Implementation:

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }
}

public class FastSlowPointerExample {
    
    // Method to detect cycle in a linked list
    public static boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }

        ListNode slow = head;
        ListNode fast = head;

        // Traverse the list with two pointers
        while (fast != null && fast.next != null) {
            slow = slow.next;       // move slow pointer by 1
            fast = fast.next.next;  // move fast pointer by 2

            // If they meet, there is a cycle
            if (slow == fast) {
                return true;
            }
        }

        // If no cycle found
        return false;
    }

    // Main method to test the fast and slow pointer implementation
    public static void main(String[] args) {
        ListNode head = new ListNode(3);
        head.next = new ListNode(2);
        head.next.next = new ListNode(0);
        head.next.next.next = new ListNode(-4);
        head.next.next.next.next = head.next;  // Creates a cycle

        System.out.println("Does the linked list have a cycle? " + hasCycle(head));
    }
}

Explanation:

We initialize two pointers: slow, which moves one step at a time, and fast, which moves two steps at a time.
If the fast pointer reaches the end (null), there’s no cycle.
If the fast pointer "laps" the slow pointer, meaning they meet at some point, then there’s a cycle in the list.
The algorithm continues until it detects a cycle or reaches the end of the list.

Expected Output:

For the linked list in the example that contains a cycle:

Does the linked list have a cycle? true

Time Complexity:

The time complexity is O(n), where n is the number of nodes in the linked list. This is because both the slow and fast pointers traverse the list once.

Space Complexity:

The space complexity is O(1), since we only use two pointers and no extra memory that scales with the size of the list.

Big O Notation Explanation:

O(n) time complexity means the algorithm will run in linear time relative to the number of nodes in the list.
O(1) space complexity means that the algorithm uses a constant amount of extra memory, regardless of the size of the input.

The fast and slow pointers pattern is highly effective for problems involving cycles or when you need to traverse linked lists or arrays in a unique way. It avoids the extra memory overhead that simpler solutions might require.

View All Patterns Here