# LU.4 Fast & Slow Pointers

> Two pointers moving through a linked list at different speeds find the middle, the n-th node from the end, and cycles (Floyd's algorithm) in one pass with O(1) space.

Chapter: Level Up: Problem Patterns · ~40 min · medium · optional, not on the exam
URL: https://dsa.fetehadin.com/learn/fast-slow-pointers

## Mental model

Two runners on a track: the **hare** runs twice as fast as the **tortoise**.

- On a **straight road**, when the hare reaches the finish, the tortoise is exactly **halfway**. That finds the **middle** of a linked list.
- On a **circular track**, the hare eventually **laps** the tortoise and they meet. That detects a **cycle**.
- Give one runner an **n-step head start** at the same speed: when the leader finishes, the other is **n from the end**.

All three need only two pointers: **O(1) extra space**, one pass.

> Built on Chapter 4 (linked lists). Not on the exam.

## C++ code: fast-slow.cpp

```cpp
#include <iostream>
using namespace std;

struct Node { int data; Node* next; };

Node* middle(Node* head) {
    Node* slow = head;
    Node* fast = head;
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;                            // 1 step
        fast = fast->next->next;                      // 2 steps
    }
    return slow;
}

Node* nthFromEnd(Node* head, int n) {
    Node* lead = head;
    for (int i = 0; i < n; i++) { if (!lead) return nullptr; lead = lead->next; }
    Node* trail = head;
    while (lead) { lead = lead->next; trail = trail->next; }   // gap of n stays fixed
    return trail;
}

bool hasCycle(Node* head) {                           // Floyd's tortoise and hare
    Node* slow = head;
    Node* fast = head;
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;
    }
    return false;
}

int main() {
    Node* nodes[7];
    for (int i = 6; i >= 0; i--) nodes[i] = new Node{i + 1, i < 6 ? nodes[i + 1] : nullptr};
    Node* head = nodes[0];                            // 1 2 3 4 5 6 7

    cout << "middle: " << middle(head)->data << "\n";
    cout << "2nd from end: " << nthFromEnd(head, 2)->data << "\n";
    cout << "cycle? " << (hasCycle(head) ? "yes" : "no") << "\n";
    nodes[6]->next = nodes[2];                        // 7 -> 3 makes a loop
    cout << "after linking 7 -> 3, cycle? " << (hasCycle(head) ? "yes" : "no") << "\n";
    nodes[6]->next = nullptr;

    for (Node* n : nodes) delete n;
}
```

Expected output:

```text
middle: 4
2nd from end: 6
cycle? no
after linking 7 -> 3, cycle? yes
```

## Complexity

| Case | Cost |
| --- | --- |
| middle node | O(n) |
| n-th from end | O(n), one pass |
| cycle detection | O(n) |

Space: O(1)

The obvious alternatives (count first, or store visited nodes in a set) need two passes or O(n) memory.

## Videos

- [Fast and Slow Pointers in 6 Minutes](https://youtu.be/b139yf7Ik-E) (AlgoMasterIO): All the fast/slow variants in 6 minutes.
- [Linked List Cycle: Floyd's Tortoise and Hare](https://youtu.be/gBTe7lFR3vc) (NeetCode): NeetCode explains why Floyd's tortoise and hare must meet inside a cycle.
- [Middle of the Linked List](https://youtu.be/A2_ldqM4QcY) (NeetCodeIO): Middle of the Linked List, solved and explained in 5 minutes.

## Exam lens

Likely questions:

- Why does `fast` meeting `slow` prove there is a cycle?
- For an even-length list, which middle does the loop return?

Common mistakes:

- Checking only `fast->next` and not `fast` first (null dereference).
- In n-th from end, moving the lead pointer n − 1 steps instead of n.

## Quick check

1. List `1 2 3 4 5 6 7`. Where is slow when fast stops?
   A. 3
   B. 4
   C. 5
   D. 7
   Answer: B. Fast visits 1, 3, 5, 7; slow visits 1, 2, 3, 4.

2. List `1 2 3 4 5 6`. middle() returns…
   A. 3
   B. 4
   C. 6
   D. nullptr
   Answer: B. This loop returns the second middle on even lengths.

3. Why must fast and slow meet if there is a cycle?
   A. Luck
   B. Inside the loop, fast gains exactly one node per step, so the gap shrinks to 0
   C. They start together
   D. The list is sorted
   Answer: B. The gap can't jump over 0 because it shrinks by 1 each step.

## Practice

**Trace by hand.** List `1 2 3 4 5 6 7`. Find the 2nd node from the end with a lead pointer. Show both pointers each step.

Solution:

Move lead 2 steps → lead at 3, trail at 1.
Then step both: (4,2) (5,3) (6,4) (7,5) (null,6). Answer: **6**.


**Implement it.** Return the node where a cycle begins (Linked List Cycle II).

Hint: After slow and fast meet, move one pointer back to head. Step both one at a time; they meet at the cycle's start.

**Problems:**

- [Middle of the Linked List](https://leetcode.com/problems/middle-of-the-linked-list/) (easy). Hint: This page's `middle()`.
- [Linked List Cycle](https://leetcode.com/problems/linked-list-cycle/) (easy). Hint: Floyd. Check `fast && fast->next` in the loop condition.
- [Remove Nth Node From End of List](https://leetcode.com/problems/remove-nth-node-from-end-of-list/) (medium). Hint: Use a dummy node and stop the trail one node early so you can unlink.
- [Linked List Cycle II](https://leetcode.com/problems/linked-list-cycle-ii/) (medium). Hint: Meet, reset one pointer to head, then walk both at speed 1.

## Mastery checklist

- [ ] I can find the middle of a linked list in one pass.
- [ ] I can find the n-th node from the end in one pass.
- [ ] I can detect a cycle with Floyd's algorithm and explain why it works.