Skip to content
ReadMe Daily

Search articles, problems, patterns and every cheat sheet topic.

Linked List Pointer Techniques

Three techniques solve most linked list problems in O(1) extra space: fast and slow pointers, reversing links in place, and a dummy head node.

Most linked list problems come down to three techniques for moving along the list and rewiring it in place: two pointers moving at different speeds, reversing the direction of links, and a dummy node placed before the head.

The idea

A linked list is a chain of nodes. Each node holds a value and a reference, next, to the node after it. The last node's next is null.

head → [1] → [2] → [3] → [4] → null

Two facts shape every solution:

  • There are no indexes. The only way to reach the fourth node is to walk through the first three. You cannot jump to the middle or step backwards.
  • Changing the list means changing next references. Nothing is shifted along, as it would be in an array, so an insertion or removal is O(1) once you are standing in the right place.

Copying the values into an array makes most problems trivial, but costs O(n) extra space. The techniques below do the same work with a few variables.

In the examples a node is any object with value and next properties.

When to use each technique

The problem asks for Technique
The middle node, or the k-th from the end Fast and slow pointers
Whether the list loops back on itself, and where Fast and slow pointers
Reversing a list, or part of one Link reversal
Checking for a palindrome in O(1) space Find the middle, reverse the second half
Removing nodes, merging lists, building a new list Dummy head

Technique 1: fast and slow pointers

Start two pointers at the head. Move one a single step at a time and the other two steps. When the fast one reaches the end, the slow one has covered half the distance, so it is at the middle.

// The middle node. With an even number of nodes, the second of the two middles.
function middleNode(head) {
  let slow = head;
  let fast = head;
  while (fast !== null && fast.next !== null) {
    slow = slow.next;
    fast = fast.next.next;
  }
  return slow;
}

The same pair of pointers detects a cycle: a list whose last node points back to an earlier one instead of to null. Walking such a list never ends. But if the fast pointer is going round a loop, it must eventually come up behind the slow pointer and land on it, like a faster runner lapping a slower one on a track.

function hasCycle(head) {
  let slow = head;
  let fast = head;
  while (fast !== null && fast.next !== null) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) return true;
  }
  return false;
}

The fast pointer cannot jump over the slow one. Inside the loop, the gap between them shrinks by exactly one node per step, so it reaches zero.

The loop condition checks both fast and fast.next because the fast pointer takes two steps. Checking only one of them lets the second step read next of null.

To reverse a list, walk along it and turn each next reference round to point at the node before. Three variables are needed: the node being processed, the one before it, and a saved reference to the one after, because overwriting current.next would otherwise lose the rest of the list.

before:   null   [1] → [2] → [3] → null
                  ↑
               current
 
after:    null ← [1] ← [2] ← [3]
                              ↑
                           new head

The four steps, repeated for each node, are: save next, point current.next backwards, move previous forward, move current forward. Reverse Linked List works through it line by line.

Reversal is rarely the whole problem. It is a building block: reverse the second half to compare it with the first, reverse a stretch between two positions, or reverse the list in groups.

Technique 3: the dummy head

Removing a node means changing the next of the node before it. The head has no node before it, so code that removes or inserts nodes ends up with a special case for the head.

A dummy node placed in front of the head removes that case. Every real node now has a predecessor. At the end, the real head is whatever follows the dummy.

// Remove every node holding `value`.
function removeValue(head, value) {
  const dummy = { value: null, next: head };
  let previous = dummy;
 
  while (previous.next !== null) {
    if (previous.next.value === value) {
      previous.next = previous.next.next; // unlink the node
    } else {
      previous = previous.next;
    }
  }
  return dummy.next;
}

Note that previous stays where it is after an unlink. The node that slid into previous.next has not been checked yet.

Return dummy.next, not head. If the original head was removed, head still refers to a node that is no longer in the list.

Complexity

Each technique walks the list a fixed number of times.

  • Time: O(n).
  • Space: O(1). Only a few pointers are stored, however long the list is. That is the whole reason to prefer these techniques over copying the list into an array.

Common mistakes

  • Losing the rest of the list. Overwriting node.next before saving the old value cuts off everything after it. Save first.
  • Reading next of null. Before writing node.next.next, be sure both node and node.next exist.
  • Returning the old head. After a reversal or a removal the head may have changed. Return the new one.
  • Comparing values instead of nodes when detecting a cycle. Two different nodes can hold the same value. Compare the nodes themselves with ===.
  • Creating a cycle by accident. After reversing part of a list, the old first node of that part still points forwards unless it is reconnected. Draw the pointers on paper for a three-node list and check every next.
  • Forgetting the empty list and the one-node list. Both are valid inputs, and both are where null errors show up.

Practice problems

ProblemDifficultyTimeSpaceRead
Reverse Linked ListeasyO(n)O(1)Medium read: 6 min
Linked List Cycle IImediumO(n)O(1)Medium read: 7 min
Reverse Nodes in k-GrouphardO(n)O(1)Medium read: 8 min