Linked List Merge Patterns — Merge Two Sorted Lists and Reorder List

There's a recurring structure across a handful of linked list problems that, once you see it, makes everything easier: you have two lists, and you need to pick from them in some specific order. Whether it's merging k sorted lists or reordering a single list, the underlying moves are the same — dummy heads, slow/fast pointer splits, and in-place pointer rewiring.

These three problems form a natural progression. LC 21 gives you the two-list merge pattern. LC 23 forces you to scale that pattern efficiently. LC 143 combines three patterns you've seen before into one elegant pipeline.

The Dummy Head Pattern

Before getting to specific problems: the dummy head is the single most underused linked list technique. Instead of tracking "is my result list empty?", you create a fake node at position -1:

const dummy = { val: 0, next: null };
let curr = dummy;
// ... build your list by setting curr.next, then curr = curr.next
return dummy.next;

This eliminates the null-check on first insertion. Your result list always has a head (dummy), and dummy.next is the real answer. Small thing — saves a surprising number of edge case bugs.

Visualizing the Core Merge

At each step, the pointer to whichever list had the smaller head advances. The other pointer stays put. Both lists are already sorted, so the front of each list is always the minimum candidate.

Problem 1: Merge Two Sorted Lists (LC 21)

Given two sorted linked lists, merge them into one sorted list and return its head. Reuse the existing nodes — no new ListNode objects.

Brute Force: Collect, Sort, Rebuild

Gather every value into an array, sort it, then build a new list.

// Input: l1 = [1,2,4], l2 = [1,3,4]
// Output: [1,1,2,3,4,4]
 
const mergeTwoListsBrute = (l1, l2) => {
  const vals = [];
 
  let curr = l1;
  while (curr) { vals.push(curr.val); curr = curr.next; }
 
  curr = l2;
  while (curr) { vals.push(curr.val); curr = curr.next; }
 
  vals.sort((a, b) => a - b);
 
  const dummy = { next: null };
  let node = dummy;
  for (const v of vals) {
    node.next = { val: v, next: null };
    node = node.next;
  }
  return dummy.next;
};
// Time: O((n + m) log(n + m)) — sorting dominates
// Space: O(n + m) — values array plus rebuilt list

This works, but it ignores that both inputs are already sorted. You're doing O((n+m) log(n+m)) work when O(n+m) is achievable.

Optimized: Two-Pointer with Dummy Head

Since both lists are sorted, you only ever need to compare the front of each. Pick the smaller, advance that pointer, repeat.

// Input: l1 = [1,2,4], l2 = [1,3,4]
// Output: [1,1,2,3,4,4]
 
const mergeTwoLists = (l1, l2) => {
  const dummy = { val: 0, next: null };
  let curr = dummy;
 
  while (l1 && l2) {
    if (l1.val <= l2.val) {
      curr.next = l1;
      l1 = l1.next;
    } else {
      curr.next = l2;
      l2 = l2.next;
    }
    curr = curr.next;
  }
 
  // One list is exhausted — append the rest of the other directly
  curr.next = l1 ?? l2;
 
  return dummy.next;
};
// Time: O(n + m) — single pass through both lists
// Space: O(1) — pointer rewiring only, no new nodes

The curr.next = l1 ?? l2 line is worth pausing on. When one list runs dry, the remaining nodes of the other are already sorted — so you can attach the entire tail in one assignment. No loop needed.

Problem 2: Merge K Sorted Lists (LC 23)

Now you have k sorted linked lists. Merge them all into one sorted list.

The naive move is to merge them sequentially: result = merge(lists[0], lists[1]), then result = merge(result, lists[2]), and so on. That's O(Nk) because early nodes get reprocessed in each round.

Brute Force: Sequential Pairwise Merge

// Input: lists = [[1,4,5],[1,3,4],[2,6]]
// Output: [1,1,2,3,4,4,5,6]
 
const mergeKListsBrute = (lists) => {
  if (!lists.length) return null;
  let result = lists[0];
  for (let i = 1; i < lists.length; i++) {
    result = mergeTwoLists(result, lists[i]);
  }
  return result;
};
// Time: O(N * k) — N total nodes, each may be processed k times
// Space: O(1) — pointer rewiring

With k=1000 lists of n=1000 nodes each, this is 10^6 * 10^3 = 10^9 operations. Unacceptable.

Optimized: Divide and Conquer

Merge lists in pairs, halving the active count each round. O(log k) rounds, each touching N total nodes → O(N log k).

// Input: lists = [[1,4,5],[1,3,4],[2,6]]
// Output: [1,1,2,3,4,4,5,6]
 
const mergeKLists = (lists) => {
  if (!lists.length) return null;
 
  while (lists.length > 1) {
    const merged = [];
 
    for (let i = 0; i < lists.length; i += 2) {
      const l1 = lists[i];
      const l2 = i + 1 < lists.length ? lists[i + 1] : null;
      merged.push(mergeTwoLists(l1, l2));
    }
 
    lists = merged;
  }
 
  return lists[0];
};
// Time: O(N log k) — log k merge rounds, N total nodes per round
// Space: O(k) — the first round allocates a merged array of ceil(k/2) entries.
//   (The recursive top-down variant is O(log k) instead, for the call stack.)

With k=1000 and N=10^6, this is 10^6 * 10 = 10^7 node visits instead of 10^9 — two orders of magnitude fewer, which is the gap between "passes" and "times out" on a judge.

Problem 3: Reorder List (LC 143)

Given L0 → L1 → … → Ln-1 → Ln, reorder it in-place to L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …

This is the hardest of the three. Most people stall because they try to handle the reordering directly, chasing nodes by index — which is O(n²) and fragile. The clean approach decomposes it:

1. Find the middle using fast/slow pointers
2. Reverse the second half in-place
3. Merge the two halves by interleaving

Each step is a pattern you've seen before. Together they solve a problem that seems to require random access.

Solution

// Input: head = [1,2,3,4,5]
// Output: [1,5,2,4,3] — modified in-place, no return value
 
const reorderList = (head) => {
  if (!head || !head.next) return;
 
  // Step 1: Find middle using fast/slow pointers
  let slow = head;
  let fast = head;
  while (fast.next && fast.next.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
  // slow is now at the last node of the first half
 
  // Step 2: Reverse the second half
  let prev = null;
  let curr = slow.next;
  slow.next = null;  // Sever the connection between halves
 
  while (curr) {
    const next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }
  // prev is now the head of the reversed second half
 
  // Step 3: Interleave first half with reversed second half
  let first = head;
  let second = prev;
 
  while (second) {
    const nextFirst = first.next;
    const nextSecond = second.next;
 
    first.next = second;
    second.next = nextFirst;
 
    first = nextFirst;
    second = nextSecond;
  }
};
// Time: O(n) — three linear passes
// Space: O(1) — all in-place pointer manipulation

A few things worth noting. The slow.next = null cut is critical — without it, your reversed second half still has a pointer back into the first half, and the interleave creates a cycle. Always cut first.

In Step 3, you save both nextFirst and nextSecond before overwriting any pointers. Order matters: set first.next = second first (consuming the second pointer), then second.next = nextFirst (consuming the first). Then advance both iterators.

Interview Tips

Call the pattern before coding. In a live interview, before touching LC 143, say: "I'm going to split this into three passes — find the middle, reverse the back half, then interleave." Naming the decomposition out loud signals you've actually thought about it, not just started hacking.

On dummy heads: Every time you need to build a result list from scratch, reflexively reach for const dummy = { val: 0, next: null }. Don't think about it. The alternative — tracking a head that might be null for the first insertion — invites bugs.

On merge K: If your interviewer asks about k lists and you give sequential pairwise merge, they will ask "what's the time complexity?" The answer O(Nk) is the cue to upgrade. Divide-and-conquer is the clean answer, and it directly reuses mergeTwoLists you just wrote.

Pointer save-before-overwrite reflex: In any linked list pointer swap, save next pointers before you modify anything. The pattern is always: const save = curr.next; curr.next = newTarget; curr = save;. In the reorder problem there are two pointers to save simultaneously — don't let one slip.

What interviewers check for: On LC 21, they want O(1) space. On LC 23, they want O(N log k) — either divide-and-conquer or heap. On LC 143, they want the three-step decomposition, not an index-chasing approach. Know what the "gold standard" is for each.