Merge Two Sorted Lists
The Prompt
You are given the heads of two sorted linked lists `list1` and `list2`. Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists. Return the head of the merged linked list.
Understanding the Problem
You get two lists that are each already sorted, and must splice their nodes into one sorted list — no new nodes, just rewired pointers. Because both inputs are sorted, the globally smallest remaining node is always one of the two current heads, so a single comparison decides the next node every time.
The classic annoyance is the very first node: before anything is merged there is no "previous node" to attach to. A dummy head node solves that — the tail pointer starts at the dummy, every append is the same tail.next = winner, and the real answer is dummy.next.
The Interview Flow
Interviewer
Given two sorted linked lists, how would you merge them into a single sorted list?
Candidate
I can solve this iteratively. I would create a dummy head node to simplify the code, as it gives me a fixed starting point. Then I'll have a `tail` pointer, initially pointing to the dummy head.
Interviewer
How does the merging process work?
Candidate
I'll iterate as long as both lists are not empty. I compare the values of the current nodes of `list1` and `list2`. I append the smaller node to my `tail.next`, and then I advance the pointer of the list from which I took the node, as well as my `tail` pointer.
Interviewer
What happens when one of the lists becomes empty?
Candidate
Once the loop finishes, one of the lists might still have remaining nodes. Since that list is already sorted, I can simply append the rest of it to my `tail.next`. Finally, I return `dummy.next`, which is the true head of the merged list.
Interviewer
That's a clean and efficient iterative solution. What about a recursive one?
Candidate
Recursively, the base cases are if either list is null, I return the other. Otherwise, I compare the heads. If `list1.val` is smaller, I know it's the next node. So, I set `list1.next` to be the result of a recursive call to merge `list1.next` and `list2`. Then I return `list1`. A similar logic applies if `list2.val` is smaller.
Interviewer
Both are correct. Let's implement the iterative one.
Why does repeatedly taking the smaller head stay sorted?
The invariant: the merged chain behind tail is sorted and contains exactly the nodes consumed so far, and every node still waiting in either list is ≥ everything already merged. Taking the smaller of the two heads is the only choice that preserves this — the other head and everything after it are at least as large, so nothing smaller can appear later.
When one list runs dry, the survivor is already sorted and entirely ≥ the merged chain, so appending it wholesale in O(1) is safe. Each node is examined once: O(n + m) time, O(1) extra space. The recursive version is the same comparisons in disguise but pays O(n + m) call-stack space.
Iterative Solution with a Dummy Node
- Create a dummy `ListNode` to serve as the starting point of the merged list.
- Create a `tail` pointer, initially pointing to the dummy node.
- Loop while both `list1` and `list2` are not null.
- Inside the loop, compare `list1.val` and `list2.val`.
- If `list1.val <= list2.val`, set `tail.next = list1`, then advance `list1` to `list1.next`.
- Otherwise, set `tail.next = list2`, then advance `list2` to `list2.next`.
- In both cases, advance the `tail` pointer to `tail.next`.
- After the loop, one of the lists may have remaining nodes. Append the non-null list to `tail.next`.
- Return `dummy.next`.
Try it yourself
Write your solution and run it against 3 test cases.
JavaScript, TypeScript & Python run sandboxed in your browser; other languages run on the execution server. Your code is saved locally as you type.
Final Solution
function mergeTwoLists(list1, list2) {
const dummy = new ListNode();
let tail = dummy;
while (list1 && list2) {
if (list1.val < list2.val) {
tail.next = list1;
list1 = list1.next;
} else {
tail.next = list2;
list2 = list2.next;
}
tail = tail.next;
}
if (list1) {
tail.next = list1;
} else if (list2) {
tail.next = list2;
}
return dummy.next;
}Explanation
Merge list1 = 1 → 2 → 4 and list2 = 1 → 3 → 4 by always splicing the smaller head onto the tail.
1Setup: tail sits at the dummy node. Compare the heads: 1 vs 1 — a tie, so take from list1 (either is valid).
2Three comparisons later the chain is dummy → 1 → 1 → 2. Now compare l1 = 4 vs l2 = 3: 3 is smaller, so it is spliced next.
3After splicing 3 then 4, list1 is empty. Append the remainder of list2 (just 4) in one pointer assignment.
4Done: 1 → 1 → 2 → 3 → 4 → 4. Return dummy.next — the dummy node vanishes and the merged head is exactly right.
Complexity Analysis
TIME
O(m + n)
SPACE
O(1)
Finished working through this one?
Mark it complete to track it on your Data Structures path.