Introduction

The Fast & Slow pointer approach, also known as the Hare & Tortoise algorithm, is a pointer algorithm that uses two pointers which move through the array (or sequence/LinkedList) at different speeds. This approach is quite useful when dealing with cyclic LinkedLists or arrays.

By moving at different speeds (say, in a cyclic LinkedList), the algorithm proves that the two pointers are bound to meet. The fast pointer should catch the slow pointer once both the pointers are in a cyclic loop.

Approach

1. Create fast and slow pointer.
2. Move fast → fast.next.next and slow → slow.next. They will meet if list has a cycle.

Base case

var slow = head;
var fast = head;

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

Find cycle node case

If we need to find cycle node, we can take head and slow(cycle pointer) and iterate till they meet, cause the gap between them has cycle size.

var slow = head;
var fast = head;
while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;

    if (slow == fast) {
        var slow2 = head;
        while (slow2 != slow) {
            slow = slow.next;
            slow2 = slow2.next;
        }
        return slow;
    }
}

List of questions

Untitled

Complexities

Usually we're looking for O(N) time and O(1) space.

Links

How does Floyd's slow and fast pointers approach work? - GeeksforGeeks