Fast and Slow Pointers (Floyd's Cycle Detection)

1. Cycle Detection in Linked Lists

Algorithm	Approach	Time	Space
Floyd's Algorithm	Fast moves 2 steps, slow moves 1 step	`O(n)`	`O(1)`
HashSet Method	Store visited nodes in set	`O(n)`	`O(n)`
Collision Point	If cycle exists, fast catches slow	Within cycle length	Meeting point inside cycle
Why It Works	Distance closes by 1 each iteration in cycle	Guaranteed meeting	Fast gains 1 step per iteration on slow

Example: Floyd's cycle detection algorithm

function hasCycle(head) {
    if (!head || !head.next) return false;
    
    let slow = head;
    let fast = head;
    
    while (fast && fast.next) {
        slow = slow.next;        // Move 1 step
        fast = fast.next.next;   // Move 2 steps
        
        if (slow === fast) {
            return true; // Cycle detected
        }
    }
    
    return false; // No cycle
}

// Time: O(n), Space: O(1)
// If cycle exists, they meet in at most n steps

Example: Alternative with HashSet (for comparison)

function hasCycleHashSet(head) {
    const visited = new Set();
    let current = head;
    
    while (current) {
        if (visited.has(current)) {
            return true; // Found cycle
        }
        visited.add(current);
        current = current.next;
    }
    
    return false;
}

// Time: O(n), Space: O(n) - less efficient than Floyd's

2. Find Middle of Linked List

Scenario	Technique	Result	Use Case
Odd Length List	When fast reaches end, slow at middle	Exact middle node	1→2→3→4→5, middle = 3
Even Length List	Slow at second middle	Right of two middle nodes	1→2→3→4, middle = 3
Single Node	Return head	Head itself is middle	Edge case handling
Two Nodes	Return second node	Fast reaches end, slow at 2nd	1→2, middle = 2

Example: Find middle node

function middleNode(head) {
    let slow = head;
    let fast = head;
    
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
    }
    
    return slow;
}

// Odd: 1→2→3→4→5 -> 3
// Even: 1→2→3→4 -> 3
// Returns second middle for even

Example: Delete middle node

function deleteMiddle(head) {
    if (!head || !head.next) return null;
    
    let slow = head;
    let fast = head;
    let prev = null;
    
    while (fast && fast.next) {
        prev = slow;
        slow = slow.next;
        fast = fast.next.next;
    }
    
    // Delete middle node
    prev.next = slow.next;
    return head;
}

3. Palindrome Linked List Verification

Step	Operation	Complexity	Purpose
1. Find Middle	Use fast-slow pointers	`O(n/2)`	Locate midpoint of list
2. Reverse Second Half	Reverse from middle to end	`O(n/2)`	Prepare for comparison
3. Compare Halves	Compare first half with reversed second	`O(n/2)`	Check if values match
4. Restore (Optional)	Reverse second half back to original	`O(n/2)`	Restore input list structure

Example: Check if linked list is palindrome

function isPalindrome(head) {
    if (!head || !head.next) return true;
    
    // Step 1: Find middle using fast-slow pointers
    let slow = head;
    let fast = head;
    
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
    }
    
    // Step 2: Reverse second half
    let prev = null;
    while (slow) {
        const next = slow.next;
        slow.next = prev;
        prev = slow;
        slow = next;
    }
    
    // Step 3: Compare first and reversed second half
    let left = head;
    let right = prev;
    
    while (right) { // Right is shorter or equal
        if (left.val !== right.val) {
            return false;
        }
        left = left.next;
        right = right.next;
    }
    
    return true;
}

// 1→2→2→1 -> true
// 1→2→3→2→1 -> true
// 1→2→3 -> false

4. Intersection of Two Linked Lists

Approach	Strategy	Complexity	Key Insight
Two Pointers Sync	Traverse both lists, switch at end	`O(m+n)`, `O(1)`	Equal path length after switching
Length Difference	Calculate lengths, align starting points	`O(m+n)`, `O(1)`	Advance longer list by difference
HashSet	Store nodes from one list, check other	`O(m+n)`, `O(m or n)`	Trade space for simplicity
Path Equalization	A→B + B→A = same length as B→A + A→B	Meet at intersection	Both traverse combined length

Example: Find intersection node (elegant two-pointer)

function getIntersectionNode(headA, headB) {
    if (!headA || !headB) return null;
    
    let pA = headA;
    let pB = headB;
    
    // Traverse both lists
    // When reaching end, switch to other list's head
    while (pA !== pB) {
        pA = pA ? pA.next : headB;
        pB = pB ? pB.next : headA;
    }
    
    return pA; // Either intersection node or null
}

// Why it works:
// If intersection exists:
//   pA: a1→a2→c1→c2→c3→(switch)→b1→b2→b3→c1 (meet here)
//   pB: b1→b2→b3→c1→c2→c3→(switch)→a1→a2→c1 (meet here)
// If no intersection:
//   Both reach null at same time

Example: Intersection with length calculation

function getIntersectionNodeByLength(headA, headB) {
    const getLength = (head) => {
        let len = 0;
        while (head) {
            len++;
            head = head.next;
        }
        return len;
    };
    
    let lenA = getLength(headA);
    let lenB = getLength(headB);
    
    // Align starting points
    while (lenA > lenB) {
        headA = headA.next;
        lenA--;
    }
    while (lenB > lenA) {
        headB = headB.next;
        lenB--;
    }
    
    // Move together until intersection
    while (headA !== headB) {
        headA = headA.next;
        headB = headB.next;
    }
    
    return headA;
}

5. Duplicate Detection in Arrays O(1) Space

Constraint	Technique	Complexity	Problem Type
Array [1, n]	Treat as linked list, values as indices	`O(n)`, `O(1)`	Find duplicate in array of n+1 elements
Floyd's in Array	slow = arr[slow], fast = arr[arr[fast]]	`O(n)`, `O(1)`	Cycle detection where duplicate creates cycle
No Constraints	HashSet to track seen elements	`O(n)`, `O(n)`	General duplicate detection
Sorted Array	Adjacent comparison or binary search	`O(n)` or `O(log n)`	Duplicates are adjacent

Example: Find duplicate number using Floyd's algorithm

function findDuplicate(nums) {
    // Treat array as linked list: index -> value
    // Duplicate creates a cycle
    
    // Phase 1: Detect cycle
    let slow = nums[0];
    let fast = nums[0];
    
    do {
        slow = nums[slow];
        fast = nums[nums[fast]];
    } while (slow !== fast);
    
    // Phase 2: Find cycle entrance (duplicate)
    slow = nums[0];
    while (slow !== fast) {
        slow = nums[slow];
        fast = nums[fast];
    }
    
    return slow;
}

// nums = [1,3,4,2,2]
// Index: 0→1, 1→3, 2→4, 3→2, 4→2 (cycle: 2→4→2)
// Output: 2

Note: The duplicate detection works because if nums[i] = nums[j] where i ≠ j, then following the "linked list" indices leads to a cycle. The entrance to this cycle is the duplicate value.

6. Find Starting Point of Cycle

Phase	Action	Mathematical Basis	Result
Phase 1: Detection	Fast-slow meet inside cycle	Distance from start to meeting = k × cycle_length	Confirm cycle exists
Phase 2: Find Start	Reset slow to head, both move at same speed	Distance from head to start = distance from meet to start	They meet at cycle start
Proof	Let L = dist to cycle, C = cycle length	When they meet: 2×slow = fast = L + kC	Remaining distance = L
Cycle Length	Keep one pointer fixed, count steps	Count iterations until pointers meet again	Optional: determine cycle size

Example: Find cycle start position

function detectCycleStart(head) {
    let slow = head;
    let fast = head;
    
    // Phase 1: Detect if cycle exists
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
        
        if (slow === fast) {
            // Cycle detected, find start
            
            // Phase 2: Find cycle entrance
            slow = head;
            while (slow !== fast) {
                slow = slow.next;
                fast = fast.next;
            }
            
            return slow; // Cycle start
        }
    }
    
    return null; // No cycle
}

// Mathematical proof:
// Let L = distance from head to cycle start
// Let C = cycle length
// Let X = distance from cycle start to meeting point
// When they meet: Fast traveled 2×distance of Slow
// Fast: L + nC + X (n loops in cycle)
// Slow: L + X
// Therefore: 2(L + X) = L + nC + X
// Simplify: L = nC - X
// So distance from head to start = (cycle length - meeting distance)

Example: Find cycle length

function getCycleLength(head) {
    let slow = head;
    let fast = head;
    
    // Detect cycle
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
        
        if (slow === fast) {
            // Found cycle, now count length
            let count = 1;
            let current = slow.next;
            
            while (current !== slow) {
                count++;
                current = current.next;
            }
            
            return count;
        }
    }
    
    return 0; // No cycle
}

Floyd's Algorithm Variations

Basic Cycle Detection: Check if slow === fast
Cycle Start: Reset one pointer, move both at same speed
Cycle Length: Keep one fixed, count until they meet
Array Duplicate: Treat values as next pointers

Why Floyd's Algorithm Works

Fast pointer gains 1 step per iteration on slow
Inside cycle, gap decreases by 1 each step
Guaranteed to meet within cycle length iterations
Math: Distance equality proves cycle start location

Note: Fast-slow pointer pattern achieves O(1) space complexity for problems that would otherwise require O(n) space with HashSet. The key insight is using speed differential to detect patterns like cycles and middle elements.

Warning: Always check both fast and fast.next before accessing fast.next.next to prevent null pointer errors. For array-based Floyd's, ensure array values are valid indices to avoid out-of-bounds access.

Related Cheat Sheets

Datastructures Algorithms