11.05Beginner / Intermediate6 topics18 min6 interactive animations

Fast/slow pointer

The fast and slow pointer technique solves many list problems in one pass and O(1) space: the middle node, the n-th node from the end, cycle detection, the cycle entry, the cycle length and palindrome checks.

Learning goals

Find the middle with two pointers at different speeds
Find the n-th node from the end with a gap
Detect a cycle and locate its entry and length with Floyd's algorithm
Check a list for a palindrome in place

Prerequisites

Singly linked operations

11.05.1

Middle node

Move slow one node and fast two nodes per step. When fast reaches the end, slow has covered half the distance and sits at the middle. For an even length this version returns the second of the two middle nodes. One pass, O(n) time, O(1) space, with no need to know the length.

Compare the odd-length and even-length presets.

Java

1static Node middle(Node head) {
2    Node slow = head, fast = head;
3    while (fast != null && fast.next != null) {
4        slow = slow.next;
5        fast = fast.next.next;
6    }
7    return slow;
8}

Fast and slow pointers: middle node and n-th from the end

Interactive · edit the input

linked list · 5 nodes

null

slow

fast

slowAnswerfast

Setup

Both pointers start at the head. Fast moves two nodes per step, slow one, so when fast reaches the end slow is in the middle.

Step 1 / 4

Java

1static Node middle(Node head) {                         // second middle when the length is even
2    Node slow = head, fast = head;
3    while (fast != null && fast.next != null) {
4        slow = slow.next;               // one step
5        fast = fast.next.next;          // two steps
6    }
7    return slow;
8}
9static Node nthFromEnd(Node head, int n) {
10    Node fast = head, slow = head;
11    for (int i = 0; i < n; i++) fast = fast.next;           // open a gap of n nodes
12    while (fast != null) { slow = slow.next; fast = fast.next; }   // the gap is kept until fast falls off the end
13    return slow;
14}

Live state

slow

fast

No condition evaluated on this step

Execution trace (dry run table)Show 4 steps

Step	Line	State	What happens
1	L2	slow=1 fast=1	Both pointers start at the head. Fast moves two nodes per step, slow one, so when fast reaches the end slow is in the middle.
2	L5	slow=2 fast=3	slow moves 1, fast moves 2: slow = 2, fast = 3.
3	L5	slow=3 fast=5	slow moves 1, fast moves 2: slow = 3, fast = 5.
4	L7	return=3	fast has no next node: slow is the middle, 3. For an even length this is the second of the two middle nodes. One pass, O(n) time, O(1) space.

11.05.2

Nth from end

To find the n-th node from the end in one pass, advance fast n nodes first, then move fast and slow together. When fast falls off the end, slow is exactly n nodes from the end because the gap between them never changed. Deleting that node needs the previous one, so stop one step earlier or use a dummy head.

Choose the n-th from the end task in the animation.

Java

1static Node nthFromEnd(Node head, int n) {
2    Node fast = head, slow = head;
3    for (int i = 0; i < n; i++) fast = fast.next;       // open a gap of n nodes (n must not exceed the length)
4    while (fast != null) { slow = slow.next; fast = fast.next; }
5    return slow;
6}

Fast and slow pointers: middle node and n-th from the end

Interactive · edit the input

linked list · 5 nodes

null

slow

fast

slowAnswerfast

Setup

Both pointers start at the head. Fast moves two nodes per step, slow one, so when fast reaches the end slow is in the middle.

Step 1 / 4

Java

1static Node middle(Node head) {                         // second middle when the length is even
2    Node slow = head, fast = head;
3    while (fast != null && fast.next != null) {
4        slow = slow.next;               // one step
5        fast = fast.next.next;          // two steps
6    }
7    return slow;
8}
9static Node nthFromEnd(Node head, int n) {
10    Node fast = head, slow = head;
11    for (int i = 0; i < n; i++) fast = fast.next;           // open a gap of n nodes
12    while (fast != null) { slow = slow.next; fast = fast.next; }   // the gap is kept until fast falls off the end
13    return slow;
14}

Live state

slow

fast

No condition evaluated on this step

Execution trace (dry run table)Show 4 steps

Step	Line	State	What happens
1	L2	slow=1 fast=1	Both pointers start at the head. Fast moves two nodes per step, slow one, so when fast reaches the end slow is in the middle.
2	L5	slow=2 fast=3	slow moves 1, fast moves 2: slow = 2, fast = 3.
3	L5	slow=3 fast=5	slow moves 1, fast moves 2: slow = 3, fast = 5.
4	L7	return=3	fast has no next node: slow is the middle, 3. For an even length this is the second of the two middle nodes. One pass, O(n) time, O(1) space.

11.05.3

Floyd cycle detection

If a list has a cycle, a fast pointer (two steps) and a slow pointer (one step) must meet inside it: once both are in the loop the gap between them shrinks by one each step. If fast reaches null, there is no cycle. Floyd's tortoise-and-hare algorithm uses O(n) time and O(1) space, whereas remembering visited nodes in a hash set needs O(n) space.

Run the default list, where the tail links back to node 3.

Java

1static boolean hasCycle(Node head) {
2    Node slow = head, fast = head;
3    while (fast != null && fast.next != null) {
4        slow = slow.next;
5        fast = fast.next.next;
6        if (slow == fast) return true;
7    }
8    return false;
9}

Floyd's cycle detection: detect, find the entry, measure the loop

Interactive · edit the input

linked list · 6 nodes

null

slow

fast

slow (tortoise)fast (hare)Cycle entry

Setup

The tail links back to node 3. The hare moves two steps, the tortoise one; inside a cycle the gap shrinks by one each step, so they must meet.

Step 1 / 13

Java

1static int detect(Node head) {                           // returns the cycle length, or -1
2    Node slow = head, fast = head;
3    while (fast != null && fast.next != null) {
4        slow = slow.next; fast = fast.next.next;
5        if (slow == fast) break;                          // they can only meet inside a cycle
6    }
7    if (fast == null || fast.next == null) return -1;      // fast reached the end: no cycle
8    Node entry = head;                                    // phase 2: restart one pointer at the head
9    while (entry != slow) { entry = entry.next; slow = slow.next; }   // meet again exactly at the entry
10    int length = 1;                                       // phase 3: walk around once
11    for (Node p = entry.next; p != entry; p = p.next) length++;
12    return length;
13}

Live state

slow

fast

No condition evaluated on this step

Execution trace (dry run table)Show 13 steps

Step	Line	State	What happens
1	L2	slow=3 fast=3	The tail links back to node 3. The hare moves two steps, the tortoise one; inside a cycle the gap shrinks by one each step, so they must meet.
2	L4	slow=2 fast=0	slow = 2, fast = 0: not the same node yet.
3	L4	slow=0 fast=7	slow = 0, fast = 7: not the same node yet.
4	L4	slow=4 fast=0	slow = 4, fast = 0: not the same node yet.
5	L4	slow=7 fast=7	Both pointers are on node 7: they met, so there is a cycle.
6	L8	entry=3 slow=7	Phase 2: keep slow at the meeting point and restart a second pointer at the head. If the head is a steps from the entry and the meeting point is a steps from it around the loop, both then reach the entry together.
7	L9	entry=2 slow=9	Move both one step: entry = 2, slow = 9.
8	L9	entry=0 slow=0	Move both one step: entry = 0, slow = 0.
9	L9	entry=0	They meet at node 0: the first node of the cycle.
10	L11	length=2	Walk around the loop: 2 nodes counted so far.
11	L11	length=3	Walk around the loop: 3 nodes counted so far.
12	L11	length=4	Walk around the loop: 4 nodes counted so far.
13	L12	entry=0 return=4	The cycle starts at node 0 (position 3) and has 4 nodes.

11.05.4

Cycle entry

To find where the cycle begins, restart one pointer at the head and keep the other at the meeting point; advance both one step at a time and they meet exactly at the entry node. Reason: if the entry is a steps from the head and the meeting point is b steps past the entry, then a + b is a multiple of the cycle length, so walking a more steps from the meeting point lands on the entry.

Phase 2 in the animation shows the two pointers converging on the entry.

Java

1static Node cycleEntry(Node head) {
2    Node slow = head, fast = head;
3    while (fast != null && fast.next != null) {
4        slow = slow.next; fast = fast.next.next;
5        if (slow == fast) {
6            Node entry = head;
7            while (entry != slow) { entry = entry.next; slow = slow.next; }
8            return entry;
9        }
10    }
11    return null;
12}

Floyd's cycle detection: detect, find the entry, measure the loop

Interactive · edit the input

linked list · 6 nodes

null

slow

fast

slow (tortoise)fast (hare)Cycle entry

Setup

The tail links back to node 3. The hare moves two steps, the tortoise one; inside a cycle the gap shrinks by one each step, so they must meet.

Step 1 / 13

Java

1static int detect(Node head) {                           // returns the cycle length, or -1
2    Node slow = head, fast = head;
3    while (fast != null && fast.next != null) {
4        slow = slow.next; fast = fast.next.next;
5        if (slow == fast) break;                          // they can only meet inside a cycle
6    }
7    if (fast == null || fast.next == null) return -1;      // fast reached the end: no cycle
8    Node entry = head;                                    // phase 2: restart one pointer at the head
9    while (entry != slow) { entry = entry.next; slow = slow.next; }   // meet again exactly at the entry
10    int length = 1;                                       // phase 3: walk around once
11    for (Node p = entry.next; p != entry; p = p.next) length++;
12    return length;
13}

Live state

slow

fast

No condition evaluated on this step

Execution trace (dry run table)Show 13 steps

Step	Line	State	What happens
1	L2	slow=3 fast=3	The tail links back to node 3. The hare moves two steps, the tortoise one; inside a cycle the gap shrinks by one each step, so they must meet.
2	L4	slow=2 fast=0	slow = 2, fast = 0: not the same node yet.
3	L4	slow=0 fast=7	slow = 0, fast = 7: not the same node yet.
4	L4	slow=4 fast=0	slow = 4, fast = 0: not the same node yet.
5	L4	slow=7 fast=7	Both pointers are on node 7: they met, so there is a cycle.
6	L8	entry=3 slow=7	Phase 2: keep slow at the meeting point and restart a second pointer at the head. If the head is a steps from the entry and the meeting point is a steps from it around the loop, both then reach the entry together.
7	L9	entry=2 slow=9	Move both one step: entry = 2, slow = 9.
8	L9	entry=0 slow=0	Move both one step: entry = 0, slow = 0.
9	L9	entry=0	They meet at node 0: the first node of the cycle.
10	L11	length=2	Walk around the loop: 2 nodes counted so far.
11	L11	length=3	Walk around the loop: 3 nodes counted so far.
12	L11	length=4	Walk around the loop: 4 nodes counted so far.
13	L12	entry=0 return=4	The cycle starts at node 0 (position 3) and has 4 nodes.

11.05.5

Cycle length

Once any node inside the cycle is known (for example the meeting point), walk once around it counting nodes until you return to it: that count is the cycle length. Together with the entry you can also compute the length of the part before the cycle.

The animation counts the loop in its last phase.

Java

1static int cycleLength(Node inside) {
2    int len = 1;
3    for (Node p = inside.next; p != inside; p = p.next) len++;
4    return len;
5}

Floyd's cycle detection: detect, find the entry, measure the loop

Interactive · edit the input

linked list · 6 nodes

null

slow

fast

slow (tortoise)fast (hare)Cycle entry

Setup

The tail links back to node 3. The hare moves two steps, the tortoise one; inside a cycle the gap shrinks by one each step, so they must meet.

Step 1 / 13

Java

1static int detect(Node head) {                           // returns the cycle length, or -1
2    Node slow = head, fast = head;
3    while (fast != null && fast.next != null) {
4        slow = slow.next; fast = fast.next.next;
5        if (slow == fast) break;                          // they can only meet inside a cycle
6    }
7    if (fast == null || fast.next == null) return -1;      // fast reached the end: no cycle
8    Node entry = head;                                    // phase 2: restart one pointer at the head
9    while (entry != slow) { entry = entry.next; slow = slow.next; }   // meet again exactly at the entry
10    int length = 1;                                       // phase 3: walk around once
11    for (Node p = entry.next; p != entry; p = p.next) length++;
12    return length;
13}

Live state

slow

fast

No condition evaluated on this step

Execution trace (dry run table)Show 13 steps

Step	Line	State	What happens
1	L2	slow=3 fast=3	The tail links back to node 3. The hare moves two steps, the tortoise one; inside a cycle the gap shrinks by one each step, so they must meet.
2	L4	slow=2 fast=0	slow = 2, fast = 0: not the same node yet.
3	L4	slow=0 fast=7	slow = 0, fast = 7: not the same node yet.
4	L4	slow=4 fast=0	slow = 4, fast = 0: not the same node yet.
5	L4	slow=7 fast=7	Both pointers are on node 7: they met, so there is a cycle.
6	L8	entry=3 slow=7	Phase 2: keep slow at the meeting point and restart a second pointer at the head. If the head is a steps from the entry and the meeting point is a steps from it around the loop, both then reach the entry together.
7	L9	entry=2 slow=9	Move both one step: entry = 2, slow = 9.
8	L9	entry=0 slow=0	Move both one step: entry = 0, slow = 0.
9	L9	entry=0	They meet at node 0: the first node of the cycle.
10	L11	length=2	Walk around the loop: 2 nodes counted so far.
11	L11	length=3	Walk around the loop: 3 nodes counted so far.
12	L11	length=4	Walk around the loop: 4 nodes counted so far.
13	L12	entry=0 return=4	The cycle starts at node 0 (position 3) and has 4 nodes.

11.05.6

Palindrome linked list

To test whether a list reads the same forwards and backwards in O(1) space: find the middle with fast and slow pointers, reverse the second half in place, then compare the two halves node by node. Restore the list afterwards if the caller still needs it. Copying the values to an array is simpler but uses O(n) space.

Run the odd and even palindrome presets and the non-palindrome.

Java

1static boolean isPalindrome(Node head) {
2    Node slow = head, fast = head;
3    while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; }
4    Node prev = null, curr = slow;
5    while (curr != null) { Node next = curr.next; curr.next = prev; prev = curr; curr = next; }   // reverse the second half
6    for (Node a = head, b = prev; b != null; a = a.next, b = b.next) if (a.val != b.val) return false;
7    return true;
8}

Palindrome list and reorder list (middle, reverse, combine)

Interactive · edit the input

linked list · 5 nodes

null

head

slow

fast

slow / compared nodefast / second halfMatching pairMismatch

Setup

Plan: find the middle, reverse the second half in place, then compare the two halves from the outside in. O(n) time, O(1) space.

Step 1 / 11

Java

1static boolean isPalindrome(Node head) {
2    Node slow = head, fast = head;
3    while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; }   // slow = middle
4    Node prev = null, curr = slow;
5    while (curr != null) { Node next = curr.next; curr.next = prev; prev = curr; curr = next; }   // reverse the second half
6    for (Node a = head, b = prev; b != null; a = a.next, b = b.next)
7        if (a.val != b.val) return false;
8    return true;                                   // callers that still need the list should re-reverse the second half
9}
10static void reorder(Node head) {                   // L0 L1 ... Ln  ->  L0 Ln L1 Ln-1 ...
11    Node slow = head, fast = head;
12    while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; }
13    Node prev = null, curr = slow.next; slow.next = null;     // cut after the first half
14    while (curr != null) { Node next = curr.next; curr.next = prev; prev = curr; curr = next; }
15    for (Node a = head, b = prev; b != null; ) {              // weave the two halves together
16        Node an = a.next, bn = b.next; a.next = b; b.next = an; a = an; b = bn;
17    }
18}

Live state

No condition evaluated on this step

Execution trace (dry run table)Show 11 steps

Step	Line	State	What happens
1	L2		Plan: find the middle, reverse the second half in place, then compare the two halves from the outside in. O(n) time, O(1) space.
2	L3	slow=2 fast=3	slow = 2, fast = 3.
3	L3	slow=3 fast=1	slow = 3, fast = 1.
4	L4		Reverse the second half with the usual three-pointer loop.
5	L5		Flip 3 to point at null.
6	L5		Flip 2 to point at 3.
7	L5		Flip 1 to point at 2.
8	L7	a=1 b=1	1 = 1: the outer pair matches.
9	L7	a=2 b=2	2 = 2: the outer pair matches.
10	L7	a=3 b=3	3 = 3: the outer pair matches.
11	L8	return=true	Every pair matched: the list is a palindrome. (The second half is still reversed; undo that if the list is used again.)

Practice ladder

Now try it yourself

Easy

Find the middle of 1 → 2 → 3 → 4 → 5 by hand
What does the fast pointer return for a null list?

Medium

Remove the n-th node from the end using a dummy head
Explain why the slow and fast pointers must meet in a cycle

Advanced

Prove that restarting a pointer at the head finds the cycle entry

Key takeaways

Two speeds find the middle; a fixed gap finds the n-th from the end.
Floyd: fast and slow meet iff there is a cycle; restart at the head to find the entry.
Palindrome: middle, reverse the second half, compare.