All Roadmaps›🧠 Data Structures & Algorithms›Phase 3›Fast & Slow Pointers (Floyd's Cycle Detection)

Fast & Slow Pointers (Floyd's Cycle Detection)

0/12 in this phase0/57 across the roadmap

📖 Concept

The fast and slow pointer technique (also called Floyd's Tortoise and Hare) uses two pointers moving at different speeds. It's the standard approach for cycle detection and finding middle elements.

Core applications:

  1. Cycle detection in linked list — fast moves 2, slow moves 1. If cycle exists, they meet.
  2. Find cycle start — after meeting, reset one pointer to head. Both move 1 step. They meet at cycle start.
  3. Find middle of linked list — when fast reaches end, slow is at middle.
  4. Happy number — detect cycles in the number sequence.
  5. Find duplicate — Floyd's applied to index-value mapping (LeetCode 287).

Why it works (cycle detection):

  • If there's a cycle of length C, after slow enters the cycle, fast catches up by 1 step per iteration (fast's relative speed is 1).
  • They must meet within C steps after slow enters the cycle.
  • Time: O(n), Space: O(1) — no hash set needed!

🏠 Real-world analogy: Two runners on a circular track — the faster runner will eventually lap the slower one. If the track is not circular (no cycle), the fast runner reaches the end first.

💻 Code Example

codeTap to expand ⛶
1// DETECT CYCLE — O(n) time, O(1) space
2function hasCycle(head) {
3  let slow = head, fast = head;
4  while (fast && fast.next) {
5    slow = slow.next;
6    fast = fast.next.next;
7    if (slow === fast) return true; // Cycle detected!
8  }
9  return false; // Fast reached end — no cycle
10}
11

12// FIND CYCLE START
13function detectCycleStart(head) {
14  let slow = head, fast = head;
15  while (fast && fast.next) {
16    slow = slow.next;
17    fast = fast.next.next;
18    if (slow === fast) {
19      // Reset slow to head, move both at speed 1
20      slow = head;
21      while (slow !== fast) {
22        slow = slow.next;
23        fast = fast.next;
24      }
25      return slow; // Meeting point = cycle start
26    }
27  }
28  return null;
29}
30

31// FIND MIDDLE OF LINKED LIST
32function findMiddle(head) {
33  let slow = head, fast = head;
34  while (fast && fast.next) {
35    slow = slow.next;
36    fast = fast.next.next;
37  }
38  return slow; // Slow is at middle when fast reaches end
39}
40

41// HAPPY NUMBER — Detect cycle in number sequence
42function isHappy(n: number): boolean {
43  function sumOfSquares(num: number): number {
44    let sum = 0;
45    while (num > 0) {
46      const digit = num % 10;
47      sum += digit * digit;
48      num = Math.floor(num / 10);
49    }
50    return sum;
51  }
52

53  let slow = n, fast = n;
54  do {
55    slow = sumOfSquares(slow);
56    fast = sumOfSquares(sumOfSquares(fast));
57  } while (slow !== fast);
58

59  return slow === 1; // 1 → 1 is a cycle of length 1
60}
61

62// FIND DUPLICATE NUMBER — Floyd's on array index mapping
63function findDuplicate(nums: number[]): number {
64  // Treat as linked list: index → value → next index
65  let slow = nums[0], fast = nums[0];
66

67  // Phase 1: Find meeting point
68  do {
69    slow = nums[slow];
70    fast = nums[nums[fast]];
71  } while (slow !== fast);
72

73  // Phase 2: Find entrance (duplicate)
74  slow = nums[0];
75  while (slow !== fast) {
76    slow = nums[slow];
77    fast = nums[fast];
78  }
79  return slow;
80}

🏋️ Practice Exercise

Practice Problems:

  1. Detect if a linked list has a cycle
  2. Find the start of the cycle in a linked list
  3. Find the middle node of a linked list
  4. Check if a number is happy (sum of square of digits → 1)
  5. Find the duplicate number in [1..n] array with n+1 elements
  6. Check if a linked list is a palindrome using fast/slow pointers
  7. Split a linked list into two halves using fast/slow
  8. Find the intersection node of two linked lists
  9. Remove the nth node from the end of a linked list in one pass
  10. Reorder list: L0→Ln→L1→Ln-1→L2→Ln-2...

⚠️ Common Mistakes

  • Dereferencing null — always check fast && fast.next before moving fast two steps

  • Forgetting to check for no-cycle case — fast reaches null means no cycle

  • Not resetting slow to head in phase 2 of cycle detection — both must move at speed 1

  • Applying Floyd's to problems without cyclic structure — it only works when there's a cycle

  • Confusing the meeting point with the cycle start — they are NOT the same (phase 1 vs phase 2)

💼 Interview Questions

🎤 Mock Interview

Practice a live interview for Fast & Slow Pointers (Floyd's Cycle Detection)

← PreviousBinary Search — Advanced ApplicationsNext →Divide and Conquer