Frontend Beauty
ESC

Type to search the knowledge base.

Merge Two Sorted Lists

Merge two sorted linked lists into one sorted list — dummy head, two pointers, O(n+m) time.

beginner3 min read
  • dsa
  • linked-list
  • interview
  • Google
  • Meta
  • Amazon

The problem

Merge two sorted singly linked lists into one sorted list. Return the head. Prefer splicing existing nodes (not new values).

Input:  1→2→4 , 1→3→4
Output: 1→1→2→3→4→4

Node shape

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

Brute force

Dump both into an array, sort, rebuild. O((n+m) log(n+m)), wastes sorted order.

Optimal: dummy + two pointers

function mergeTwoLists(
  list1: ListNode | null,
  list2: ListNode | null
): ListNode | null {
  const dummy = new ListNode(0);
  let tail = dummy;

  while (list1 && list2) {
    if (list1.val <= list2.val) {
      tail.next = list1;
      list1 = list1.next;
    } else {
      tail.next = list2;
      list2 = list2.next;
    }
    tail = tail.next;
  }

  tail.next = list1 ?? list2;
  return dummy.next;
}

Recursive:

function mergeTwoListsRec(
  a: ListNode | null,
  b: ListNode | null
): ListNode | null {
  if (!a) return b;
  if (!b) return a;
  if (a.val <= b.val) {
    a.next = mergeTwoListsRec(a.next, b);
    return a;
  }
  b.next = mergeTwoListsRec(a, b.next);
  return b;
}
Time O(n + m)
Space O(1) iterative / O(n+m) recursive stack

Edge cases

  • Both empty → null
  • One empty → the other
  • All of one list smaller than the other
  • Duplicates — either order fine if stable-ish with <=

Common bugs

  • Forgetting to attach the remainder (tail.next = list1 ?? list2)
  • Returning dummy instead of dummy.next
  • Losing references by advancing before linking

Interview delivery

  1. Dummy head avoids empty-head special cases.
  2. Always take the smaller of the two heads.
  3. Attach leftover.
  4. O(n+m), O(1).
  5. Mention merge-k lists as follow-up.

Dry-run

1→2→4 and 1→3→4:

  1. dummy tail takes first 1 from list1
  2. then 1 from list2
  3. then 2, 3, 4, 4
  4. return dummy.next

Dummy head value

The dummy’s val is ignored. Use 0 or any sentinel. Without dummy you’d special-case “which list starts first” and keep a separate head reference — more bugs under pressure.

Recursive stack risk

Elegant recursion is O(n+m) stack frames. Fine for interview-scale lists; in production prefer iterative. Say that once so they know you notice.

Follow-ups

  • Merge k sorted lists (heap or divide-and-conquer).
  • Merge sorted arrays in-place from the back.
  • Sort a linked list (merge sort on lists).

Further reading