LU.4 ~40 min mediumoptional · not on the exam

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.

Rule of this site: Don't just watch: implement it yourself, then solve 2–3 problems.

02Mental 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.

03Visualize

space play · ←→ step · r reset. The highlighted code line follows each step.

Loading visualizer…

Find the middle, then detect a cycle, then find the n-th node from the end.

04C++ code

Compiled and run with g++ -std=c++17; the output below is real. Type it out yourself before you copy it.

fast-slow.cpp48 lines · C++17

Compiler ExplorerRun OnlineGDB

#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;
}

#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

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

05Complexity

middle node	O(n)
n-th from end	O(n), one pass
cycle detection	O(n)
Extra space	O(1)

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

06Watch

Fast and Slow Pointers in 6 Minutes

AlgoMasterIO · 6:09

Why this one: All the fast/slow variants in 6 minutes.

Watched

Linked List Cycle: Floyd's Tortoise and Hare

NeetCode · 10:44

Why this one: NeetCode explains why Floyd's tortoise and hare must meet inside a cycle.

Watched

Middle of the Linked List

NeetCodeIO · 4:57

Why this one: Middle of the Linked List, solved and explained in 5 minutes.

Watched

Original class slides (Python, by the course's lecture authors):Linked List (fast & slow)

07Exam 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.

08Quick check

1.List 1 2 3 4 5 6 7. Where is slow when fast stops?
2.List 1 2 3 4 5 6. middle() returns…
3.Why must fast and slow meet if there is a cycle?

09Practice

🟢 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.

Show answer

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.

🔴 Solve problems

Middle of the Linked List easyleetcode.com
Hint
This page's middle().
Linked List Cycle easyleetcode.com
Hint
Floyd. Check fast && fast->next in the loop condition.
Remove Nth Node From End of List mediumleetcode.com
Hint
Use a dummy node and stop the trail one node early so you can unlink.
Linked List Cycle II mediumleetcode.com
Hint
Meet, reset one pointer to head, then walk both at speed 1.

10Mastery checklist

Tick these honestly. When every box is ticked, the topic is marked complete.

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.

0/3 ticked

My notes

View as Markdown