Merge Two Sorted Lists

EasyLinked ListLinked ListRecursion

Problem

You are given the heads of two linked lists, each already sorted in non-decreasing order. Combine them into a single sorted list by reusing the existing nodes (no new nodes, and no rebuilding from scratch) and return its head.

Example. Merging 1 -> 2 -> 4 with 1 -> 3 -> 4 produces 1 -> 1 -> 2 -> 3 -> 4 -> 4.

Key idea

Because both inputs are already sorted, there is no need to collect every value and sort them again: that would cost an unnecessary O((n+m) log(n+m)) when the lists already carry the ordering information. Instead, walk both lists at once and compare only the two nodes currently at the front. Splice whichever one is smaller onto the result, then advance that list's pointer by one; the other pointer stays put for the next comparison.

A dummy placeholder node before the real result avoids special-casing which list contributes the first node: everything gets appended after the dummy, and the answer is the node after it. Once one list runs dry, the remaining list is already sorted, so its remainder can be attached directly rather than walked node by node.

Solution

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

function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {
  const dummy = new ListNode(); // placeholder head, keeps the loop free of special cases
  let tail = dummy;

  while (list1 !== null && list2 !== null) {
    if (list1.val <= list2.val) {
      tail.next = list1; // splice the smaller node onto the result
      list1 = list1.next;
    } else {
      tail.next = list2;
      list2 = list2.next;
    }
    tail = tail.next;
  }

  tail.next = list1 !== null ? list1 : list2; // remainder is already sorted, attach it as-is

  return dummy.next;
}

Complexity

  • Time: O(n + m). Each node from both lists is visited and compared exactly once.
  • Space: O(1) beyond the output. Existing nodes are relinked rather than copied, aside from the small overhead of the dummy node.

Watch out for

  • Compare node values, not node references, and remember <= and < both work as long as the tie-break is consistent.
  • After the loop ends, attach whichever list still has nodes left directly: looping element by element for the remainder is unnecessary and easy to get wrong.
  • Do not forget to detach the dummy node before returning; the answer is dummy.next, not dummy itself.

Pattern

This two-pointer merge is the core building block of merge sort and generalizes directly to combining more than two sorted sequences, as in merging k sorted lists.

Related questions