Fast & slow pointers

The two-pointer technique known as the Tortoise and Hare advances two reference cursors through a list at different velocities: slow steps 1 node per iteration while fast steps 2 nodes per iteration (fast = fast.next.next). This 2:1 velocity differential allows single-pass inspection of structural properties without pre-computing list length.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

// Finding Left Middle for Clean Bisecting
public ListNode getLeftMiddle(ListNode head) {
    if (head == null) return null;
    ListNode slow = head;
    ListNode fast = head;

    // Terminates with slow at first middle for even lengths
    while (fast.next != null && fast.next.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }

    return slow;
}

Floyd’s Cycle-Finding Algorithm determines whether a linked list contains a cycle using strictly O(1) auxiliary memory. Rather than maintaining a hash set of visited memory addresses (which consumes O(n) heap memory), the 2:1 runner speed difference mathematically guarantees detection.

1. 01Phase 1: Both pointers enter the cycle. Let the cycle have length L.
2. 02Phase 2: Once slow enters the cycle, fast is already somewhere inside the cycle.
3. 03Phase 3: Consider the relative distance d between fast and slow measured along the direction of traversal (0 <= d < L).
4. 04Phase 4: In every discrete time step, slow moves +1 and fast moves +2. The relative distance decreases by (2 - 1) = 1 step per tick modulo L.
5. 05Phase 5: Because the gap closes by strictly 1 unit each step, the distance must hit exactly 0 mod L in at most L iterations. Fast can never hop over slow without colliding.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

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;         // 1 step
        fast = fast.next.next;    // 2 steps

        if (slow == fast) {
            return true; // Collision confirms cycle existence
        }
    }

    return false; // Fast reached terminal null: linear chain
}

Once Floyd’s algorithm detects a collision between slow and fast, we can locate the exact starting node of the cycle in O(n) time and O(1) space using an elegant mathematical symmetry.

1. 01At collision: distance(slow) = a + b.
2. 02At collision: distance(fast) = a + b + n * L (where n >= 1 is the number of full cycle loops completed by fast).
3. 03Since fast moves at twice the speed of slow: distance(fast) = 2 * distance(slow).
4. 04Substitute: a + b + n * L = 2 * (a + b) => a + b + n * L = 2a + 2b.
5. 05Simplify: a = n * L - b.
6. 06Decompose n * L: Since L = b + c, we rewrite n * L - b = (n - 1) * L + (L - b) = (n - 1) * L + c.
7. 07Conclusion: a = (n - 1) * L + c. The distance from the list head to the cycle entrance (a) equals the distance from the collision point to the cycle entrance (c), plus (n - 1) full cycle revolutions!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

public ListNode detectCycle(ListNode head) {
    if (head == null || head.next == null) return null;

    ListNode slow = head;
    ListNode fast = head;

    // 1. Detect collision
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            // 2. Derive cycle start: reset ptr1 to head, keep ptr2 at collision
            ListNode ptr1 = head;
            ListNode ptr2 = slow;

            // Both step at 1 node per iteration until meeting at entrance
            while (ptr1 != ptr2) {
                ptr1 = ptr1.next;
                ptr2 = ptr2.next;
            }
            return ptr1; // Cycle entrance node
        }
    }

    return null; // No cycle
}