Merge Sorted Linked Lists

Given two already-sorted linked lists, the goal is to produce a single sorted list by relinking existing nodes — no new node allocations needed.

Node Class

class ListNode {
  constructor(val = 0, next = null) {
    this.val = val;
    this.next = next;
  }
}

Iterative Merge With a Dummy Head

Create a temporary dummy node whose next will become the merged list’s head. Keep a curr pointer that always sits at the last node of the result built so far.

function mergeTwoLists(l1, l2) {
  const dummy = new ListNode(-Infinity);
  let curr = dummy;

  while (l1 !== null && l2 !== null) {
    if (l1.val <= l2.val) {
      curr.next = l1;
      l1 = l1.next;
    } else {
      curr.next = l2;
      l2 = l2.next;
    }
    curr = curr.next;
  }

  // At least one list is exhausted; attach the remainder.
  curr.next = l1 !== null ? l1 : l2;

  return dummy.next;  // discard the dummy sentinel
}

The dummy node eliminates the “what is the head of the result?” question that clutters the code otherwise. It is the same sentinel trick used in the doubly linked list lesson.

Recursive Merge

The recursive version expresses the same logic without an explicit cursor:

function mergeTwoListsRecursive(l1, l2) {
  if (l1 === null) return l2;
  if (l2 === null) return l1;

  if (l1.val <= l2.val) {
    l1.next = mergeTwoListsRecursive(l1.next, l2);
    return l1;
  } else {
    l2.next = mergeTwoListsRecursive(l1, l2.next);
    return l2;
  }
}

Elegant, but uses O(n + m) stack frames. For very long lists the iterative version is safer in JavaScript.

Example

// List A: 1 → 3 → 5
// List B: 2 → 4 → 6
const a = new ListNode(1, new ListNode(3, new ListNode(5)));
const b = new ListNode(2, new ListNode(4, new ListNode(6)));

const merged = mergeTwoLists(a, b);

let curr = merged;
while (curr) { process.stdout.write(curr.val + " "); curr = curr.next; }
// Output: 1 2 3 4 5 6

Complexity

k-Way Merge (Teaser)

When you have k sorted lists instead of two, repeatedly applying mergeTwoLists in sequence costs O(nk) where n is the total number of nodes. A min-heap (priority queue) reduces this to O(n log k):

1. Push the head of every list into a min-heap keyed on node value.
2. Pop the smallest node, append it to the result, and push its successor (if any) back into the heap.
3. Repeat until the heap is empty.

The heap always holds at most k entries, so each push/pop is O(log k), and with n total nodes the overall cost is O(n log k). The full implementation is covered in the Heaps chapter.

Up Next

Move on to stacks — a simpler linked-list-backed structure with O(1) push and pop — and see how the call stack itself mirrors this abstraction.