Linked lists: walking and rewiring pointers

A linked list is a chain of nodes where each node only knows the next one. You can't jump to position 5. You have to walk there. So the main skill is moving a few named pointers, such as prev, cur, fast and slow. A pointer here is a variable that refers to a node. You change next links without losing the rest of the chain.

Think of it like this: a treasure hunt. Each clue only tells you where the next clue is hidden. To reach clue 5 you must follow clues 1 to 4. If you rewrite a clue before reading it, the rest of the trail is lost.

How to spot it

Words and constraints in a problem that point to this pattern:

• The input is a ListNode called head, not an array
• “Reverse”, “reorder”, “remove the nth node from the end”, “merge two sorted lists”
• “Does it loop back on itself?”, “find the middle”, “where do two lists meet?”
• “Use O(1) extra space” on a list: rewire the links instead of copying into an array

Watch it work

The template

class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val: number, next: ListNode | null = null) {
    this.val = val;    // the data this node holds
    this.next = next;  // the node after this one, or null at the end
  }
}

// 1. Walk: no indexes, so follow next until null. Use your own pointer, not head.
function toArray(head: ListNode | null): number[] {
  const out: number[] = [];
  for (let node = head; node !== null; node = node.next) out.push(node.val);
  return out;
}

// 2. Dummy head: keep only the even values, without a special case for the first node.
function keepEven(head: ListNode | null): ListNode | null {
  const dummy = new ListNode(0);  // fake node in front; its value is never used
  let tail = dummy;               // the last node we decided to keep
  for (let node = head; node !== null; node = node.next) {
    if (node.val % 2 === 0) {
      tail.next = node;           // attach the kept node
      tail = node;                // it becomes the new tail
    }
  }
  tail.next = null;               // cut off whatever followed the last kept node
  return dummy.next;              // the real head (null if nothing was kept)
}

// 3. Reverse: prev / cur / next.
function reverse(head: ListNode | null): ListNode | null {
  let prev: ListNode | null = null;  // the reversed part so far
  let cur = head;                    // the node we are about to flip
  while (cur !== null) {
    const next = cur.next;           // bookmark the rest before breaking the link
    cur.next = prev;                 // flip the arrow backwards
    prev = cur;                      // the reversed part now starts at cur
    cur = next;                      // move on to the rest
  }
  return prev;                       // the old tail is the new head
}

// 4. Fast and slow: fast moves 2 steps for each 1 step of slow.
function walkFastSlow(head: ListNode | null): void {
  let slow = head;
  let fast = head;
  while (fast !== null && fast.next !== null) {  // check fast.next before using fast.next.next
    slow = slow!.next;                           // 1 step
    fast = fast.next.next;                       // 2 steps
  }
  // no cycle: fast has reached the end, and slow is halfway along
}

Worked example

1. The first idea, which is fine to say out loud: count the nodes in one walk, then walk again to position Math.floor(count / 2). This takes two passes and O(1) space. Copying into an array and indexing also works, but it costs O(n) space.

   function middleTwoPasses(head: ListNode | null): ListNode | null {
     let count = 0;
     for (let n = head; n !== null; n = n.next) count++;
     let node = head;
     for (let i = 0; i < Math.floor(count / 2); i++) node = node!.next;
     return node;
   }
   

2. Notice the waste: the first pass only exists to learn where the end is. If a second runner moves twice as fast, then when it reaches the end, the first runner has covered exactly half the distance. That's one pass.

3. Fast and slow pointers. Both start at the head. Each round, slow takes one step and fast takes two. Stop when fast can't take two more steps.

   function middle(head: ListNode | null): ListNode | null {
     let slow = head;
     let fast = head;
     while (fast !== null && fast.next !== null) {
       slow = slow!.next;       // 1 step
       fast = fast.next.next;   // 2 steps
     }
     return slow;
   }
   

4. Run 1 → 2 → 3 → 4 → 5: (slow 1, fast 1) → (2, 3) → (3, 5). Now fast.next is null, so stop: node 3. Run 1 → 2 → 3 → 4: (1, 1) → (2, 3) → (3, null). fast is null, so stop: node 3, the second middle, as asked.

5. Edge cases: a single node has fast.next === null, so the loop never runs and the head is returned. An empty list returns null. Checking fast !== null first is what stops “Cannot read properties of null”.

Common mistakes

• Changing cur.next before saving it: the rest of the list becomes unreachable, and the reversed list has only one node.
• Returning head after reversing: the old head is now the tail, so you return the one-node list 1 → null.
• Checking fast.next.next without first checking fast.next: on an even-length list fast becomes null and the code crashes with “Cannot read properties of null”.
• Handling the first node with a separate if branch and getting that branch wrong. A dummy node in front turns the head into an ordinary node.
• Walking with the head variable itself: after the loop head is null, and you can no longer return the list. Walk with a separate pointer.

Cost

In interviews