Overview#

Linked list two pointers are a set of techniques centered around moving node references. Because linked lists cannot be randomly accessed by index, many operations that are simple in arrays—such as “find the midpoint,” “find the k-th from the end,” or “determine whether two lists intersect”—must be accomplished in linked lists through pointer speed or distance.

The most common linked list two-pointer patterns include:

• Fast and slow pointers: one moves fast, one moves slow;
• Front and back pointers: two pointers maintain a fixed distance;
• Synchronized pointers: two pointers move synchronously according to a rule across different linked lists.

Prerequisites

• Linked list nodes: can only move forward unidirectionally along next
• Fast and slow pointers: use speed difference to create a distance relationship
• Dummy head node: unify boundary handling when deleting nodes

Problem Definition#

Linked list two pointers mainly solve three types of problems:

The commonality of these problems is that they cannot rely on length or index for direct positioning; relationships can only be established through the movement process.

Core Principle: Step-by-Step Diagram#

1
slow moves 1 step each time
2
fast moves 2 steps each time

1
1 -> 2 -> 3 -> 4 -> 5 -> null
2
          ^
3
         slow

1
A -> B -> C -> D
2
     ^         |
3
     |---------|

Detailed Algorithm Steps#

General steps for linked list two-pointer problems:

1. Clarify what relationship must be maintained between the two pointers;
2. Handle edge cases such as empty lists, single nodes, and head node deletion;
3. Move the pointers according to the rule;
4. Explain the position of each pointer when the loop ends;
5. Modify pointer connections or return the target node.

The easiest thing to get wrong is the loop condition. For example, when finding the midpoint, there are two common ways to write it:

1
while (fast !== null && fast.next !== null) {
2
  slow = slow.next;
3
  fast = fast.next.next;
4
}

This condition ensures that fast.next.next will not access a null value.

TypeScript Implementation#

1
class ListNode<T> {
2
  constructor(
3
    public value: T,
4
    public next: ListNode<T> | null = null,
5
  ) {}
6
}

1
function middleNode<T>(head: ListNode<T> | null): ListNode<T> | null {
2
  let slow = head;
3
  let fast = head;
4

5
  while (fast !== null && fast.next !== null) {
6
    slow = slow!.next;
7
    fast = fast.next.next;
8
  }
9

10
  return slow;
11
}

1
function hasCycle<T>(head: ListNode<T> | null): boolean {
2
  let slow = head;
3
  let fast = head;
4

5
  while (fast !== null && fast.next !== null) {
6
    slow = slow!.next;
7
    fast = fast.next.next;
8

9
    if (slow === fast) return true;
10
  }
11

12
  return false;
13
}

1
function removeNthFromEnd<T>(head: ListNode<T> | null, n: number): ListNode<T> | null {
2
  const dummy = new ListNode<T>(null as T, head);
3
  let fast: ListNode<T> | null = dummy;
4
  let slow: ListNode<T> | null = dummy;
5

6
  for (let i = 0; i < n; i++) {
7
    fast = fast!.next;
8
  }
9

10
  while (fast?.next !== null) {
11
    fast = fast.next;
12
    slow = slow!.next;
13
  }
14

15
  slow!.next = slow!.next!.next;
16
  return dummy.next;
17
}

Engineering Optimization: Turn Distance into an Invariant#

The essence of linked list two pointers is maintaining invariants:

• Fast and slow pointers: the distance traveled by fast is approximately equal to 2 * slow;
• Front and back pointers: fast and slow always differ by n nodes;
• Intersecting linked lists: the two pointers ultimately traverse the same length of lenA + lenB.

Intersecting linked lists can be written like this:

1
function getIntersectionNode<T>(
2
  headA: ListNode<T> | null,
3
  headB: ListNode<T> | null,
4
): ListNode<T> | null {
5
  let a = headA;
6
  let b = headB;
7

8
  while (a !== b) {
9
    a = a === null ? headB : a.next;
10
    b = b === null ? headA : b.next;
11
  }
12

13
  return a;
14
}

After the two pointers swap starting points, the path lengths are equalized, so if there is an intersection point, they will arrive at it in the same round.

Applications and Limitations#

Summary#

• Linked list two pointers use movement relationships instead of index-based positioning.
• Fast and slow pointers are suitable for finding midpoints and detecting cycles.
• Front and back pointers are suitable for problems related to positions from the end.
• Synchronized pointers can eliminate differences in linked list lengths.
• Before writing code, first define the invariant between the two pointers.