March 24
Merge Two Sorted Lists
How to notice the lists are already sorted and that the right comparison always happens at the heads.
Linked List Beginner 18 min TypeScript
Given the heads of two sorted linked lists list1 and list2, merge them into one sorted list and return its head.
Example:
Input: 1 -> 2 -> 4, 1 -> 3 -> 4
Output: 1 -> 1 -> 2 -> 3 -> 4 -> 4
What to notice before coding
- Both input lists already arrive sorted.
- At every step, the right choice is between the two current heads.
- When one list ends, the rest of the other list can be attached as-is.
Common mistakes
- forgetting to attach the remainder when one list finishes
- advancing the wrong pointer after choosing a node
Step 1 — Understand which information already came for free
The problem does not give you two arbitrary lists.
It gives you two sorted lists.
If you ignore that, you miss the best clue in the prompt.
Step 2 — Write a correct baseline
A valid baseline is to collect all values, sort them, and rebuild:
export function mergeTwoLists(list1, list2) {
const values = []
let left = list1
let right = list2
while (left) {
values.push(left.val)
left = left.next
}
while (right) {
values.push(right.val)
right = right.next
}
values.sort((a, b) => a - b)
const dummy = { val: 0, next: null }
let tail = dummy
for (const value of values) {
tail.next = { val: value, next: null }
tail = tail.next
}
return dummy.next
}
It works. But the extra sorting should not exist here.
Step 3 — Ask where the next smallest value can be
Since both lists are already sorted, the next value to place can only be in one of two spots:
- current head of
list1 - current head of
list2
You do not need to search the rest.
Step 4 — Stitch the answer while you walk
Use:
- a
dummynode to simplify the head of the answer - a
tailpointer to mark where the next node should attach
Compare the heads, attach the smaller node, and advance only the list that provided it.
The interactive editor needs JavaScript. You can still read the prompt and copy the starter code below.
Starter code
export function mergeTwoLists(list1, list2) {
// list nodes are objects like { val: number, next: ... } or null
// your solution here
return null
}
Haven't solved it yet?
Viewing the solution now may reduce learning. It's worth trying a bit more.
Open the reference solution
Without JavaScript, the reference solution is shown inline instead of in a dialog.
Solution
Final complexity
Time: O(n + m)
Space: O(1)
Solution 1 — Collect, sort, and rebuild
Useful as a baseline, but it wastes the sorted input.
export function mergeTwoLists(list1, list2) {
const values = []
let left = list1
let right = list2
while (left) {
values.push(left.val)
left = left.next
}
while (right) {
values.push(right.val)
right = right.next
}
values.sort((a, b) => a - b)
const dummy = { val: 0, next: null }
let tail = dummy
for (const value of values) {
tail.next = { val: value, next: null }
tail = tail.next
}
return dummy.next
}Solution 2 — Linear merge with pointers and a dummy head
Now the solution fully uses the fact that both lists are already sorted.
export function mergeTwoLists(list1, list2) {
const dummy = { val: 0, next: null }
let tail = dummy
let left = list1
let right = list2
while (left && right) {
if (left.val <= right.val) {
tail.next = left
left = left.next
} else {
tail.next = right
right = right.next
}
tail = tail.next
}
tail.next = left ?? right
return dummy.next
}Once one list ends, the rest of the other list is already in the right order.
What to say in the interview
A strong short explanation would be:
The baseline could collect everything and sort again, but that ignores that both lists are already sorted. So I only compare the two current heads, attach the smaller one to the answer, and advance that list. That gives a linear merge in
O(n + m).
That shows that you:
- used the input structure properly
- understood the sorted-merge pattern
- explained the solution without adding unnecessary work
When this pattern shows up again
The same pattern comes back when you need to:
- combine sorted sequences
- choose between two moving frontiers
- build an answer incrementally
- use a dummy head to simplify pointer handling
The point is not memorizing
mergeTwoLists.
The point is recognizing when sorted order is already available and only stitching is left.