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
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).
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.
Two questions come up when you write this as code:
- 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.
- 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
2 is smaller than 3, so we attach the 2 node after tail. Then list1 moves on
to its next node, 4 (list1 = list1.next). list2 is untouched: its front is still 3.
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]
- 10
new list (built back to front)
head → null (empty list)
- head
- null
- Already copied
- Just written / created
- New list
Copy 1 into the array: [1].
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 headWith 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.
Pattern
Dummy (sentinel) head node
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”
- Make
dummy(any value; we use 0) and settail = dummy. - While both lists still have nodes, compare their fronts.
- Attach the smaller front node:
tail.next = list1(orlist2), and move that list forward. - Move
tailonto the node we just attached. - When one list runs out, attach the whole other list:
tail.next = list1 or list2. - 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.
- 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".
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}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 placeholderThe 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:
tailstarts 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:
<=takeslist1on 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
tailto 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.
list1 = [1, 2, 4], list2 = [1, 3, 4]:
| list1 front | list2 front | take | merged so far |
|---|---|---|---|
| 1 | 1 | list1's 1 (tie → list1) | 1 |
| 2 | 1 | list2's 1 | 1 → 1 |
| 2 | 3 | 2 | 1 → 1 → 2 |
| 4 | 3 | 3 | 1 → 1 → 2 → 3 |
| 4 | 4 | list1's 4 (tie) | 1 → 1 → 2 → 3 → 4 |
| null | 4 | attach rest: 4 | 1 → 1 → 2 → 3 → 4 → 4 |
The last row is the leftover attach: list1 is empty, so list2’s remaining node is linked in one step, without comparing.
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.
What to say out loud:
- “Both lists are sorted, so the smallest remaining node is always one of the two fronts.”
- “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).”
- “When one list runs out, I attach the other in one step.”
- “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.