Easy difficulty · Algorithm · Topics: linked-list, two-pointers, merge, dummy-head
Merge two sorted linked lists into one sorted list by relinking their existing nodes. The lists are passed as arrays, turned into nodes inside the function, and the merged values are returned as an array. This is the "merge" step of merge sort, performed on linked lists.
Imagine two sorted piles of cards face up. Repeatedly take the smaller top card of the two piles and append it to a growing result row. When one pile is empty, the rest of the other pile is already sorted, so it can be placed on the row in one move.
On linked lists the "row" is built with a tail pointer that always sits on the last node of the result. A dummy head node placed before the real result means the very first append needs no special case: tail.next = ... always works, and the answer is dummy.next.
Invariant: the nodes from dummy.next to tail are sorted and are all smaller than or equal to every node still left in a and b.
dummy = new ListNode(0) and set tail = dummy.a and .ba.val <= b.val picks a, which keeps the merge stable) after tail, advance that list's pointer, and move tail forward.tail.next to it (no copying needed).dummy.next.Test case 0: list1 = 1 -> 3 -> 5, list2 = 2 -> 4.
| Step | a | b | Compare | Result so far |
|---|---|---|---|---|
| start | 1 | 2 | - | dummy |
| 1 | 1 | 2 | 1 <= 2, take a | 1 |
| 2 | 3 | 2 | 3 > 2, take b | 1 -> 2 |
| 3 | 3 | 4 | 3 <= 4, take a | 1 -> 2 -> 3 |
| 4 | 5 | 4 | 5 > 4, take b | 1 -> 2 -> 3 -> 4 |
| end | 5 | null | loop stops | attach the rest: ... -> 4 -> 5 |
The result is [1, 2, 3, 4, 5].
| Measure | Cost | Why |
|---|---|---|
| Time | O(n + m) | Each node of both lists is visited at most once |
| Space | O(1) | Only a few pointers; the nodes are reused, not copied (the output array is for display) |
tail after each append, so every new node overwrites the previous one.< instead of <=, which still sorts but makes the merge unstable for equal values.dummy instead of dummy.next (an extra leading 0).a, b and tail: a and b creep forward through their lists while tail extends the result.dummy list view growing node by node, with tail always on its last node.tail.next = ... line: it attaches the remaining nodes in one pointer write.Input: list1 = [1, 3, 5], list2 = [2, 4]
Output: [1, 2, 3, 4, 5]
function mergeTwoLists(values1, values2) {
const list1 = buildList(values1);
const list2 = buildList(values2);
// The dummy head removes the "is the result empty yet?" special case.
const dummy = new ListNode(0);
let tail = dummy;
let a = list1;
let b = list2;
while (a !== null && b !== null) {
// Splice the smaller node onto the end of the result.
if (a.val <= b.val) {
tail.next = a;
a = a.next;
} else {
tail.next = b;
b = b.next;
}
tail = tail.next;
}
// At most one list still has nodes: attach it whole.
tail.next = a !== null ? a : b;
const out = [];
for (let curr = dummy.next; curr !== null; curr = curr.next) {
out.push(curr.val);
}
return out;
}
function buildList(values) {
let head = null;
for (let i = values.length - 1; i >= 0; i--) {
head = new ListNode(values[i], head);
}
return head;
}