Merge Two Sorted Lists
Understand the problem
Given the head of two linked lists, both sorted in ascending order.
Merge them into a single sorted list by relinking the existing nodes, and return the new head.
// l1: 1 → 2 → 4
// l2: 1 → 3 → 4
// result: 1 → 1 → 2 → 3 → 4 → 4Since both lists are sorted, you only compare the heads of the two lists and repeatedly take the smaller node — exactly the "merge" step of merge sort.
A dummy node at the front avoids special-casing the first element.
Show the basic approach (slower)
O((n+m) log(n+m)) time, O(n+m) spacefunction mergeNaive(l1: ListNode | null, l2: ListNode | null): ListNode | null {
const vals: number[] = []
for (let n = l1; n; n = n.next) vals.push(n.val)
for (let n = l2; n; n = n.next) vals.push(n.val)
vals.sort((a, b) => a - b) // re-sort even though both lists are already sorted
const dummy = new ListNode(0)
let tail = dummy
for (const v of vals) { tail.next = new ListNode(v); tail = tail.next }
return dummy.next
}This approach gathers all values and sorts them again — wasteful since the two lists are already sorted.
Using two pointers to exploit that takes only O(n+m).
Optimal solution
O(n + m) time, O(1) spacefunction mergeTwoLists(l1: ListNode | null, l2: ListNode | null): ListNode | null {
const dummy = new ListNode(0) // dummy node to attach the result to
let tail = dummy
while (l1 && l2) {
if (l1.val <= l2.val) {
tail.next = l1
l1 = l1.next
} else {
tail.next = l2
l2 = l2.next
}
tail = tail.next
}
tail.next = l1 ?? l2 // append the remainder (one list is exhausted)
return dummy.next
}The optimal approach uses two pointers at the heads of the two lists; each step links the smaller node onto the tail of the result and advances that pointer.
- Use
<=to keep the order stable on ties. - When one list runs out, link the remainder directly because it is already sorted.
- No new nodes are created, so extra memory is O(1).
Step-by-step trace
1function mergeTwoLists(l1: ListNode | null, l2: ListNode | null): ListNode | null {2 const dummy = new ListNode(0) // dummy node to attach the result to3 let tail = dummy4 5 while (l1 && l2) {6 if (l1.val <= l2.val) {7 tail.next = l18 l1 = l1.next9 } else {10 tail.next = l211 l2 = l2.next12 }13 tail = tail.next14 }15 16 tail.next = l1 ?? l2 // append the remainder (one list is exhausted)17 return dummy.next18}Edge cases to remember
Both lists empty → dummy.next = null → return null.
One list empty → the loop does not run, link the other list directly.
Every element of l1 is smaller than l2 → l1 runs out first, and the tail is all of l2.
Equal values across the two lists → use <= to keep the order stable.