Learn › DSA Patterns

Pattern #4 · Linked List · O(N) Time O(1) Space

Fast & Slow
Pointers

Learn how Floyd's Tortoise and Hare detects cycles, finds midpoints, and more — in O(N) time, O(1) space.

🔄 Cycle detection 🎯 Find middle node 🐢 Floyd's algorithm

Scroll to learn

Story Time

The Tortoise and the Hare 🐢🐇

Before writing a single line of code, let's understand the intuition through a story.

🏁

The Race Begins

In a coding wonderland, Tim the Tortoise and Harry the Hare started a race on a long array track. Tim moved one step at a time while Harry jumped two steps at a time. Simple enough — until something strange happened.

😲

Harry Meets Tim Again

Harry kept sprinting ahead — then suddenly found himself face-to-face with Tim again in the middle of the track. "Wait, how did you catch up?" Tim asked. "I don't know! I just kept running ahead," Harry replied, confused.

🧙

The Wise Coder's Insight

A wise old coder watching nearby smiled: "Aha! You must be running in a cycle! If Harry keeps lapping Tim, they'll always meet — it's mathematically guaranteed."

✗ No cycle → Harry reaches the end and stops. They never meet.
✓ Cycle exists → Harry laps Tim. They always meet inside the loop.

📍

Visualising the Pointers

Here's the same idea on a linked list with a cycle from node F back to node C:

A 🐢 slow

→

C cycle start

→

E 🐇 fast

→

↩ back to C

🚀

Moral of the story

Two pointers, one data structure. If there's a cycle, the fast pointer always catches up to the slow pointer — in O(N) time using only O(1) extra space. No hash sets needed!

Interactive

Cycle Visualizer

Watch slow and fast pointers traverse the linked list step-by-step.

Initial state: slow=A, fast=A. List: A→B→C→D→E→F→C (cycle at C).

slow fast meeting point cycle start

slow = slow.next Slow moves 1 step

fast = fast.next.next Fast moves 2 steps

slow === fast Cycle detected

Complexity

Three Approaches

Approach	Time	Space	Best for
Hash Set	O(N)	O(N)	Simple, readable
Fast & Slow Preferred ✓	O(N)	O(1)	Memory-constrained
Visited Array	O(N)	O(N)	Arrays only, bounded indices

Fast & Slow uses zero extra memory — no hash set, no visited array. That's the key advantage over the alternatives.

TypeScript

Implementation

Three patterns, from basic to advanced.

// O(N) time, O(1) space — Floyd's Tortoise and Hare
class ListNode {
  value: number;
  next: ListNode | null;
  constructor(value: number, next: ListNode | null = null) {
    this.value = value;
    this.next = next;
  }
}

function hasCycle(head: ListNode | null): boolean {
  let slow = head;          // tortoise: 1 step at a time
  let fast = head;          // hare:     2 steps at a time

  while (fast !== null && fast.next !== null) {
    slow = slow!.next;      // move one step
    fast = fast.next.next!; // move two steps

    if (slow === fast) {
      return true; // they met — cycle exists!
    }
  }

  return false; // fast hit null — no cycle
}

// Test
console.log(hasCycle(circularList)); // → true
console.log(hasCycle(linearList));   // → false

// Find middle of a linked list — O(N) time, O(1) space
// When fast reaches the end, slow is at the middle
function findMiddle(head: ListNode | null): ListNode | null {
  let slow = head;
  let fast = head;

  while (fast !== null && fast.next !== null) {
    slow = slow!.next;      // 1 step
    fast = fast.next.next!; // 2 steps
  }

  return slow; // slow is at the middle node
}

// Odd  [1→2→3→4→5] → returns node 3  (exact middle)
// Even [1→2→3→4]   → returns node 3  (second middle)
//
// Trace [1,2,3,4,5]:
//   start:  slow=1, fast=1
//   step 1: slow=2, fast=3
//   step 2: slow=3, fast=5  (fast.next=null → exit loop)
//   return 3  ✓
console.log(findMiddle(list)?.value); // → 3

// Floyd's Cycle II — find the START node of the cycle
// Phase 1: detect meeting point.  Phase 2: find entry.
function detectCycle(head: ListNode | null): ListNode | null {
  let slow = head, fast = head;

  // Phase 1: find the meeting point
  while (fast !== null && fast.next !== null) {
    slow = slow!.next;
    fast = fast.next.next!;

    if (slow === fast) {
      // Phase 2: find cycle entry node
      slow = head;         // reset slow to head
      while (slow !== fast) {
        slow = slow!.next; // both advance 1 step
        fast = fast!.next;
      }
      return slow;         // cycle start node
    }
  }

  return null; // no cycle
}

// Why Phase 2 works:
// Let F = distance head → cycle start
//     C = cycle length
// Meeting point is exactly F steps from cycle start.
// Reset slow → head; both advance 1 step → meet at entry. ✓

Comparison

Hash Set vs Fast & Slow

🗃️ Hash Set Approach O(N) space

Detect cycle Store each node in set

Find middle Walk once, store all, pick mid

Memory usage O(N) — stores every node

Code clarity Easy to read and write

Interviews Acceptable but not optimal

🐢🐇 Fast & Slow Pointers O(1) space

Detect cycle Two pointers, no storage

Find middle One pass, stop when fast ends

Memory usage O(1) — only two pointers

Code clarity Elegant once learned

Interviews Preferred optimal solution

Practice

Solve It Yourself

Click any question to see hints and approach.

B Basic

B1 What is the Slow and Fast Pointers technique, and why is it useful? ⌄

💡 Hint

Think about what happens when two runners on a circular track have different speeds. The fast one will always lap the slow one.

✅ Answer

Floyd's Cycle Detection uses a slow pointer (1 step) and fast pointer (2 steps). If there's a cycle, they will eventually meet. If no cycle, fast reaches null first. Key benefit: O(1) space — no extra data structures needed.

B2 Given list 1→2→3→4→5 (no cycle), trace hasCycle() step by step. When does it terminate? ⌄

💡 Hint

Track both pointers. The loop exits when fast === null or fast.next === null.

✅ Answer

Start: slow=1, fast=1. Step 1: slow=2, fast=3. Step 2: slow=3, fast=5. Step 3: fast.next=null → exit loop. Return false. The fast pointer hits the end before they ever meet.

B3 Why does the fast pointer move two steps instead of any other number (e.g., three steps)? ⌄

💡 Hint

Consider the relative speed difference. If fast moved 3 steps, could it skip over slow inside a cycle?

✅ Answer

Two steps guarantees they must meet. With 3+ steps, the fast pointer could overshoot and the meeting is not guaranteed in O(N) time. With 2 steps, the gap between them shrinks by exactly 1 each iteration, ensuring they meet within one full cycle traversal.

M Intermediate

M1 LeetCode 141 — Linked List Cycle: does the list 3→1→2→0→back to 1 have a cycle? ⌄

💡 Hint

Trace slow (1 step) and fast (2 steps) through the list. Watch for when they land on the same node.

✅ Answer

Yes. Trace: start slow=3,fast=3 → slow=1,fast=2 → slow=2,fast=2. They meet at node 2. Return true.

→ Solve on LeetCode ↗

M2 LeetCode 876 — Middle of the Linked List: find the middle of [1,2,3,4,5]. ⌄

💡 Hint

Use findMiddle(). When fast hits end, slow is at the middle. Trace through the 5-node list.

✅ Answer

Node 3. Trace: slow=1,fast=1 → slow=2,fast=3 → slow=3,fast=5 (fast.next=null, exit). Return node with value 3.

→ Solve on LeetCode ↗

M3 LeetCode 287 — Find the Duplicate Number: given [1,3,4,2,2], find the duplicate using O(1) space. ⌄

💡 Hint

Treat the array as a linked list: index → value. nums[i] gives the 'next' pointer. A duplicate index creates a cycle. Apply Floyd's algorithm.

✅ Answer

2. Phase 1: slow=nums[slow], fast=nums[nums[fast]]. Start at index 0: slow:0→1→3→2→4→2, fast:0→4→2→4→2. They meet at 2. Phase 2: reset slow to 0, both move 1 step → slow=1,fast=4 → slow=3,fast=2 → slow=2,fast=2. Duplicate is 2.

→ Solve on LeetCode ↗

H Advanced

H1 LeetCode 142 — Linked List Cycle II: find the starting node of the cycle, not just whether one exists. ⌄

💡 Hint

Two phases: (1) detect meeting point with slow/fast. (2) Reset slow to head; move both one step until they meet. That meeting node is the cycle start.

✅ Answer

Mathematical proof: Let F = head-to-cycle-start distance, C = cycle length. At meeting: slow traveled F+a, fast traveled F+a+nC. Since fast=2×slow: 2(F+a)=F+a+nC → F=nC-a. So from the meeting point, going F more steps arrives at cycle start — same distance as from the head. Both pointers meet at the cycle entry.

→ Solve on LeetCode ↗

H2 LeetCode 234 — Palindrome Linked List: check if 1→2→2→1 is a palindrome using O(1) space. ⌄

💡 Hint

Find the middle (fast/slow), reverse the second half, compare both halves node by node.

✅ Answer

Step 1: findMiddle([1,2,2,1]) → node at index 2 (value 2). Step 2: reverse second half: 2→1 becomes 1→2. Step 3: compare: head=1 vs reversed=1 ✓, next: 2 vs 2 ✓. It is a palindrome. Time O(N), space O(1).

→ Solve on LeetCode ↗

H3 After detecting a cycle (slow === fast), how do you count the number of nodes inside the cycle? ⌄

💡 Hint

Keep one pointer fixed at the meeting point. Move the other one step at a time, counting until it returns to the meeting point.

✅ Answer

Fix fast at the meeting point. Move slow one step at a time, incrementing a counter, until slow === fast again. That counter is the cycle length. For a list A→B→C→D→E→F→back to C: meeting at E, count steps E→F→C→D→E = 4 nodes in cycle.

H4 Given array [2,0,1,3,4,2] where each element is the index of the 'next' node — detect if it has a cycle. ⌄

💡 Hint

Treat it as a linked list: current = arr[current]. Apply hasCycle with slow=arr[slow] and fast=arr[arr[fast]].

✅ Answer

Yes. Trace: slow=arr[0]=2, fast=arr[arr[0]]=arr[2]=1. Next: slow=arr[2]=1, fast=arr[arr[1]]=arr[0]=2. Next: slow=arr[1]=0, fast=arr[arr[2]]=arr[1]=0. slow===fast at index 0 → cycle detected. Index-value graph has a cycle 0→2→1→0.

In the Wild

Real-World Applications

📦

Logistics Systems

Package Tracking Loops

A package cycling between 'Processing' and 'Sorting Center' represents an infinite loop in the routing graph. Fast & Slow detects it without storing the entire history.

🐢🐇 How it fits: Model shipment states as nodes. If status ever cycles, fast pointer catches slow in O(N) time, O(1) space.

💾

Garbage Collectors

Memory Leak Detection

JVM and V8 garbage collectors detect circular references (object A → B → C → A) to reclaim memory. Cycle detection is core to mark-and-sweep algorithms.

🐢🐇 How it fits: Object references form a linked graph. Floyd's detects unreachable cycles that can't be freed — preventing memory leaks.

🌐

Network Routing

Routing Loop Detection

In BGP/OSPF routing, a misconfigured network can send packets in an infinite loop between routers. Detecting these loops is critical for network stability.

🐢🐇 How it fits: Routers as nodes, routes as edges. Slow & fast pointer traversal detects routing cycles before packets loop forever.

🎵

Music / Video Players

Infinite Playlist Cycle

Playlist shuffle algorithms must detect when a generated sequence loops back to a previously played song — especially in constrained embedded devices with no memory for a full history.

🐢🐇 How it fits: Songs as nodes, next-song as the pointer. O(1) cycle detection works on microcontrollers where hash sets are too expensive.

Quick Reference

Cheat Sheet

The Math

Slow pointer speed

1 step / iteration

Fast pointer speed

2 steps / iteration

Meeting guaranteed in

≤ N iterations

Cycle start (Phase 2)

F = nC − a

When to Use

✓ Detect cycle in linked list
✓ Find start of cycle
✓ Find middle of linked list
✓ Check palindrome linked list
✓ Find duplicate in array
✓ Detect cycle in array graph
✓ Split list in two halves
✓ Nth node from end (variant)

Pattern Variations

Basic Cycle

hasCycle() → return bool

Cycle Entry (Floyd II)

detectCycle() → return node

Complexity

Time: O(N)

Space: O(1)

Keep Learning

You've mastered Fast & Slow Pointers 🎉

This pattern unlocks cycle detection, palindrome checks, and duplicate finding — all in O(1) space.

← Back to Learn LeetCode Linked List Problems ↗