Skip to content
16-Week DSA Roadmap
LeetCode #21EasyProblem 5 of 8

Merge Two Sorted Lists

Zip two sorted linked lists into one sorted list by always taking the smaller front node, with a dummy node to start from.

  • Dummy (sentinel) head node
  • Two pointers on two lists

Before this, know: What a linked list is (see the week 4 overview), Following node.next in a loop

The problem in plain English

You get the heads of two linked lists, list1 and list2. Each list is already sorted from small to large. Join them into one sorted list, made by splicing together the existing nodes, and return its head.

A linked list is a chain of nodes; each node has a value val and an arrow next to the following node, and the last node points to null (None in Python).

input
124134
merged
112344
list1 = [1, 2, 4] and list2 = [1, 3, 4] merge into 1 → 1 → 2 → 3 → 4 → 4. The colours show which list each node came from.

The rules that matter:

  • Either list (or both) can be empty.
  • Values can repeat and can be negative.
  • Each list has at most 50 nodes, but the method should work for any size.

Before you code: think it through

Two questions come up when you write this as code:

  1. What is the head of the result? It’s whichever front node is smaller, but then the loop has to handle “the result is still empty” separately from “add after the last node”. Messy.
  2. Where do we attach the next node? After the last node of the result so far. So we keep a pointer to it, called tail.

The trick for question 1 is a dummy node (also called a sentinel): a fake node we create at the start, whose only job is to sit in front of the answer. The result is never “empty” because it always contains the dummy, so every node gets attached the same way: tail.next = node. At the end we return dummy.next.

Pause and think

The fronts are list1 = 2 → 4 and list2 = 3 → 4. Which node do we take next, and what happens to list1 and list2?

Approach 1: Collect, sort, rebuild

Ignore that the lists are sorted: copy every value into one array, sort it, and build a brand-new list from the sorted values. Building from the back lets us put each new node in front of the previous one, so we don’t need a tail pointer.

Brute force: collect, sort, rebuild

list1 = [1, 2, 4], list2 = [1, 3, 4]

inputs: list1 (top), list2 (bottom)
124134
values
  1. 10

new list (built back to front)

head → null (empty list)

variables
head
null
  • Already copied
  • Just written / created
  • New list

Copy 1 into the array: [1].

Step 1 / 14

Which line is running?

function mergeTwoLists(list1, list2) {  const values = [];  for (const start of [list1, list2]) {    let node = start;    while (node !== null) {Running now:       values.push(node.val);      node = node.next;    }  }  values.sort((a, b) => a - b);  let head = null;  for (let i = values.length - 1; i >= 0; i--) {    head = new ListNode(values[i], head); // build from the back, one node in front at a time  }  return head;}

Collect, sort, rebuild

function mergeTwoLists(list1, list2) {  const values = [];  for (const start of [list1, list2]) {    let node = start;    while (node !== null) {      values.push(node.val);      node = node.next;    }  }  values.sort((a, b) => a - b);  let head = null;  for (let i = values.length - 1; i >= 0; i--) {    head = new ListNode(values[i], head); // build from the back, one node in front at a time  }  return head;}
def merge_two_lists(list1, list2):    values = []    for start in (list1, list2):        node = start        while node is not None:            values.append(node.val)            node = node.next    values.sort()    head = None    for v in reversed(values):        head = ListNode(v, head)  # build from the back, one node in front at a time    return head

Why is it slow?

With n and m nodes, sorting n + m values costs about O((n + m) log(n + m)), plus an extra array and n + m new nodes. For two lists of 1,000 nodes that’s roughly 2,000 × 11 ≈ 22,000 steps of sorting work, when both lists were already sorted. And the problem asked us to splice the existing nodes, not copy them.

The pattern: dummy (sentinel) head node

Pattern

Dummy (sentinel) head node

Template

Use it when: you build a new list node by node, or might remove/replace the head, and want to avoid a special case for the first node.

Signal words

  • “merge lists”
  • “remove nodes”
  • “the head may change”
  • “build a result list”
  • “partition list”

Approach 2: Dummy node + tail pointer

  1. Make dummy (any value; we use 0) and set tail = dummy.
  2. While both lists still have nodes, compare their fronts.
  3. Attach the smaller front node: tail.next = list1 (or list2), and move that list forward.
  4. Move tail onto the node we just attached.
  5. When one list runs out, attach the whole other list: tail.next = list1 or list2.
  6. Return dummy.next.

The top row is list1, the middle row is list2, and the bottom row is the merged list growing from the dummy node D. Watch each node slide down when tail reaches it. Try the “Leftovers” example to see the final attach move a whole chain at once.

Dummy node + tail pointer

list1 = [1, 2, 4], list2 = [1, 3, 4]

Top row: list1. Middle row: list2. Bottom row: the merged list, starting at the dummy node D.

D124134
variables
list1
1node
list2
1node
dummy
Dnode
tail
Dnode
  • The two fronts being compared
  • Just linked
  • tail (end of merged list)
  • Dummy (placeholder)
  • Answer

Make a dummy node "D" (value 0, never part of the answer). The merged list will hang off it, so we never need a special case for "the merged list is still empty".

Step 1 / 24

Which line is running?

function mergeTwoLists(list1, list2) {Running now:   const dummy = new ListNode(0); // placeholder in front of the answer  let tail = dummy; // last node of the merged list so far  while (list1 !== null && list2 !== null) {    if (list1.val <= list2.val) {      tail.next = list1;      list1 = list1.next;    } else {      tail.next = list2;      list2 = list2.next;    }    tail = tail.next;  }  tail.next = list1 !== null ? list1 : list2; // attach whatever is left  return dummy.next; // skip the placeholder}

The code, line by line

Dummy node + tail

function mergeTwoLists(list1, list2) {  const dummy = new ListNode(0); // placeholder in front of the answer  let tail = dummy; // last node of the merged list so far  while (list1 !== null && list2 !== null) {    if (list1.val <= list2.val) {      tail.next = list1;      list1 = list1.next;    } else {      tail.next = list2;      list2 = list2.next;    }    tail = tail.next;  }  tail.next = list1 !== null ? list1 : list2; // attach whatever is left  return dummy.next; // skip the placeholder}
def merge_two_lists(list1, list2):    dummy = ListNode(0)  # placeholder in front of the answer    tail = dummy  # last node of the merged list so far    while list1 is not None and list2 is not None:        if list1.val <= list2.val:            tail.next = list1            list1 = list1.next        else:            tail.next = list2            list2 = list2.next        tail = tail.next    tail.next = list1 if list1 is not None else list2  # attach whatever is left    return dummy.next  # skip the placeholder

The line numbers match up to line 11; after that JavaScript’s extra } puts it one line ahead. LeetCode defines ListNode for you; in Python the function is def mergeTwoLists(self, list1, list2) inside class Solution.

  • Line 2: the dummy node. Its value never appears in the answer.
  • Line 3: tail starts on the dummy: the merged list so far is “just the dummy”.
  • Line 4: loop only while both lists have a front node to compare.
  • Line 5: <= takes list1 on a tie. Either choice gives a correct sorted result; <= also keeps equal values in their original order (a “stable” merge).
  • Lines 6–7 / 9–10: link the chosen node after tail, then advance that list. We reuse the node itself; no new nodes are created.
  • Line 12 (JS) / 11 (Py): move tail to the node we just attached, so the next node goes after it.
  • Line 14 (JS) / 12 (Py): one list is empty. The other one is already sorted and all its values are ≥ everything merged so far, so we attach the whole rest with one assignment (possibly null, if both ran out).
  • Line 15 (JS) / 13 (Py): skip the dummy and return the real head.

Dry run

list1 = [1, 2, 4], list2 = [1, 3, 4]:

list1 frontlist2 fronttakemerged so far
11list1's 1 (tie → list1)1
21list2's 11 → 1
2321 → 1 → 2
4331 → 1 → 2 → 3
44list1's 4 (tie)1 → 1 → 2 → 3 → 4
null4attach rest: 41 → 1 → 2 → 3 → 4 → 4
list1 = [1, 2, 4], list2 = [1, 3, 4]

The last row is the leftover attach: list1 is empty, so list2’s remaining node is linked in one step, without comparing.

Complexity

Collect, sort, rebuild

Time

O((n + m) log(n + m))

Sorting all n + m values dominates.

Space

O(n + m)

An extra array plus n + m new nodes.

Dummy node + tail

Time

O(n + m)

Each step attaches one node, and there are n + m nodes. Leftovers are attached in one step.

Space

O(1)

Just dummy and tail. The answer reuses the input nodes.

Common mistakes and edge cases

What to say out loud:

  1. “Both lists are sorted, so the smallest remaining node is always one of the two fronts.”
  2. “I’ll use a dummy head so I don’t need a special case for the first node, and a tail pointer to attach in O(1).”
  3. “When one list runs out, I attach the other in one step.”
  4. “O(n + m) time, O(1) extra space, and I reuse the existing nodes.”

Likely follow-ups:

  • “Do it recursively.” if list1.val <= list2.val: list1.next = merge(list1.next, list2); return list1 (and the mirror case). It’s elegant but uses O(n + m) stack space.
  • “Merge k sorted lists.” (LeetCode 23) Use a min-heap of the k fronts, or merge pairs of lists repeatedly.

Related problems:

  • Reorder List: its last phase merges two lists by alternating instead of by value.
  • Remove Nth Node From End of List: the dummy node again, this time for deleting the head.
  • Merge Sorted Array (LeetCode 88): the same merge idea on arrays.