Interview preparation
Merge Two Sorted Lists
1Problem statement
Merge two sorted linked lists into one sorted list made by splicing together the nodes of the two lists, and return its head.
2Examples
3Constraints
- 0 ≤ length of each list ≤ 50
- Both lists are sorted in non-decreasing order.
4Approaches
Approach 1
Brute Force
Collect all values, sort them, build a new list.
Approach 2
Better: Recursion
The smaller head comes first; its next is the merge of the rest.
Approach 3
Optimal: Iterative with a dummy node
Keep a tail pointer; always attach the smaller current node, then append the leftover list.
5Code (optimal approach)
Complete programs that print the example outputs — verified in JavaScript, Python, Java and Go.
class ListNode {
constructor(val, next = null) {
this.val = val;
this.next = next;
}
}
function mergeTwoLists(a, b) {
const dummy = new ListNode(0);
let tail = dummy;
while (a !== null && b !== null) {
if (a.val <= b.val) {
tail.next = a;
a = a.next;
} else {
tail.next = b;
b = b.next;
}
tail = tail.next;
}
tail.next = a !== null ? a : b;
return dummy.next;
}
function build(values) {
let head = null;
for (let i = values.length - 1; i >= 0; i--) head = new ListNode(values[i], head);
return head;
}
function show(head) {
const out = [];
for (let n = head; n !== null; n = n.next) out.push(n.val);
out.push("null");
return out.join(" -> ");
}
console.log(show(mergeTwoLists(build([1, 2, 4]), build([1, 3, 4]))));
console.log(show(mergeTwoLists(build([]), build([0]))));
6Complexity
Time
O(m + n)
Space
O(1)
7Visual walkthrough
- 1.dummy → ; compare 1 and 1 → take list1's 1
- 2.compare 2 and 1 → take 1
- 3.compare 2 and 3 → take 2
- 4.compare 4 and 3 → take 3
- 5.compare 4 and 4 → take 4, then append remaining 4
Related visualization (Singly Linked List Insertion) — shows the core data-structure operations this solution relies on:
Inserts a new node at a given position: walk to the node just before the position, point the new node at its successor, then re-link the predecessor to the new node.