DSA Patterns Made Simple · Linked Lists, Stacks and Intervals
Fast and Slow Pointers
Move one pointer one step at a time and another two steps. They find the middle of a list, detect cycles and find the nth node from the end, all in one pass with no extra memory.
The problem
Linked List Cycle: a linked list's last node may point back to an earlier node, making a loop. Walking it naively never ends. How do you tell, without storing every node you've visited?
How to spot it
- Linked list + "cycle", "loop", "middle", "nth from the end"
- "Is this sequence eventually repeating?" (e.g. the "happy number" problem, where you repeatedly apply a function)
- A constraint like O(1) extra space that rules out a
seenset
The idea
Two runners on a circular track: if one runs twice as fast, it will eventually lap the slower one. If the track has an end instead, the fast runner simply reaches it first.
- Cycle:
slowmoves 1 step,fastmoves 2. If they ever meet, there's a cycle; iffastreaches the end, there isn't. - Middle: when
fastreaches the end,slowis halfway. - Nth from the end: give
fasta head start of n steps, then move both one step at a time. Whenfasthits the end,slowis n from the end.
The template
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
return True # they met: there is a cycle
return False # fast fell off the end; slow is at the middle
let slow = head, fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) return true; // they met: there is a cycle
}
return false; // fast fell off the end; slow is at the middle
Worked example
A tiny linked list class, then middle, cycle detection and "remove the nth node from the end" with a head-start pointer.
class Node:
def __init__(self, val, next=None):
self.val, self.next = val, next
def build(values):
head = None
for v in reversed(values):
head = Node(v, head)
return head
def show(head):
out = []
while head:
out.append(str(head.val))
head = head.next
return " -> ".join(out) or "(empty)"
def middle(head):
slow = fast = head
while fast and fast.next:
slow, fast = slow.next, fast.next.next
return slow.val
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow, fast = slow.next, fast.next.next
if slow is fast:
return True
return False
def remove_nth_from_end(head, n):
dummy = Node(0, head) # handles removing the first node
slow = fast = dummy
for _ in range(n):
fast = fast.next # head start of n steps
while fast.next:
slow, fast = slow.next, fast.next
slow.next = slow.next.next # slow is just before the node to remove
return dummy.next
print("middle of 1..5:", middle(build([1, 2, 3, 4, 5])))
looped = build([3, 2, 0, -4])
looped.next.next.next.next = looped.next # -4 points back to 2
print("cycle?", "yes" if has_cycle(looped) else "no")
print("cycle in 1..5?", "yes" if has_cycle(build([1, 2, 3, 4, 5])) else "no")
print("remove 2nd from end:", show(remove_nth_from_end(build([1, 2, 3, 4, 5]), 2)))
print("remove only node:", show(remove_nth_from_end(build([1]), 1)))
Output
middle of 1..5: 3 cycle? yes cycle in 1..5? no remove 2nd from end: 1 -> 2 -> 3 -> 5 remove only node: (empty)
class Node {
constructor(val, next = null) { this.val = val; this.next = next; }
}
function build(values) {
let head = null;
for (const v of [...values].reverse()) head = new Node(v, head);
return head;
}
function show(head) {
const out = [];
for (; head; head = head.next) out.push(head.val);
return out.join(" -> ") || "(empty)";
}
function middle(head) {
let slow = head, fast = head;
while (fast && fast.next) { slow = slow.next; fast = fast.next.next; }
return slow.val;
}
function hasCycle(head) {
let slow = head, fast = head;
while (fast && fast.next) {
slow = slow.next; fast = fast.next.next;
if (slow === fast) return true;
}
return false;
}
function removeNthFromEnd(head, n) {
const dummy = new Node(0, head); // handles removing the first node
let slow = dummy, fast = dummy;
for (let i = 0; i < n; i++) fast = fast.next; // head start of n steps
while (fast.next) { slow = slow.next; fast = fast.next; }
slow.next = slow.next.next; // slow is just before the node to remove
return dummy.next;
}
console.log("middle of 1..5:", middle(build([1, 2, 3, 4, 5])));
const looped = build([3, 2, 0, -4]);
looped.next.next.next.next = looped.next; // -4 points back to 2
console.log("cycle?", hasCycle(looped) ? "yes" : "no");
console.log("cycle in 1..5?", hasCycle(build([1, 2, 3, 4, 5])) ? "yes" : "no");
console.log("remove 2nd from end:", show(removeNthFromEnd(build([1, 2, 3, 4, 5]), 2)));
console.log("remove only node:", show(removeNthFromEnd(build([1]), 1)));
Output
middle of 1..5: 3 cycle? yes cycle in 1..5? no remove 2nd from end: 1 -> 2 -> 3 -> 5 remove only node: (empty)
Common mistakes
- Checking only
fast.next. The loop condition must befast and fast.next, orfast.next.nextcrashes at the end of the list. - Comparing values instead of nodes. Two different nodes can hold the same value; compare the node objects (
is/===). - Forgetting the dummy node when the node to remove might be the head.
- Even-length lists. With
while fast and fast.next,slowends on the second of the two middle nodes. Know which one your problem wants.
Practice
- Linked List Cycle (easy)
- Remove Nth Node From End of List (medium)
Key points
- Slow moves 1, fast moves 2: they meet if there's a cycle; slow is at the middle when fast ends.
- A head start of n gives "nth from the end" in one pass.
- O(n) time and O(1) space, unlike a
seenset. - A dummy node before the head removes special cases.
Practice questions
Why must the fast pointer eventually meet the slow pointer if there's a cycle?
Answer
Once both are inside the cycle, the fast pointer gains one node on the slow pointer every step, so the gap between them shrinks by one each step until it reaches zero. It can't jump over the slow pointer.
How do you find the middle of a linked list in one pass?
Answer
Move slow one node and fast two nodes per step. When fast reaches the end (fast or fast.next is null), slow is at the middle.
Open in the app to mark lessons complete, take notes and track your progress.