🗓️ Day 9: Fast & Slow Pointers (Tortoise and Hare)

🧠 Concept Deep Dive

The Fast & Slow Pointers technique, also known as the Tortoise and Hare algorithm, is primarily used in linked lists, but it also works for cycle detection, finding mid-points, and palindrome verification. The key idea is to have one pointer move twice as fast as the other.

🔹 Core Use Cases:

• Detecting cycles in linked lists
• Finding the middle node
• Reversing half of the list
• Checking if a linked list is a palindrome

🔹 Visualization:

fast: 2 steps
slow: 1 step

If there's a loop, they will eventually meet.

🔹 Key Principles:

• Fast pointer skips ahead
• Slow pointer walks
• If a cycle exists, fast will "lap" slow

📖 Example 1: Detect Cycle in Linked List

Problem:

Given a linked list, determine if it has a cycle.

Approach:

Use two pointers:

• slow moves 1 step
• fast moves 2 steps If they ever meet, a cycle exists.

class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val?: number, next?: ListNode | null) {
    this.val = val ?? 0;
    this.next = next ?? null;
  }
}

function hasCycle(head: ListNode | null): boolean {
  let slow = head;
  let fast = head;

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

  return false;
}

Visualization:

A -> B -> C -> D -> E
          ^         \
          |----------

slow: 1 step
fast: 2 steps
Eventually meet at node in the loop

📖 Example 2: Find Middle of Linked List

Problem:

Return the middle node of a linked list. If even length, return the second middle.

function middleNode(head: ListNode | null): ListNode | null {
  let slow = head;
  let fast = head;

  while (fast && fast.next) {
    slow = slow!.next;
    fast = fast.next.next;
  }

  return slow;
}

Example:

Input: [1 -> 2 -> 3 -> 4 -> 5] => Output: 3
Input: [1 -> 2 -> 3 -> 4 -> 5 -> 6] => Output: 4

🧪 Real-world Analogy

Imagine two people running on a circular track:

• One runs slowly
• One runs fast If there's a loop, the fast one will eventually lap the slow one. If no loop, the fast runner will finish the track without catching the slow one.

📊 Big O Complexity

🧪 LeetCode-style Homework

Problem: Linked List Cycle II

Find the node where the cycle begins, or return null if no cycle exists.

Function Signature:

function detectCycle(head: ListNode | null): ListNode | null;

Hint:

• First detect if a cycle exists (using fast/slow).
• If so, move one pointer to head and advance both one step at a time — they will meet at cycle start.

📆 Summary

• Fast & Slow pointers = powerful pattern for linked lists
• Great for cycle detection, mid-point location
• Efficient in time and space

🔬 Up Next

▶️ Day 10: Sliding Window Technique