3. Merge Two Sorted Lists
easyAsked at CourseraMerge two sorted linked lists into one — Coursera uses this to test pointer hygiene in a sorted-content-streams setting.
By Sam K., Founder, InterviewChamp.AI · Last verified
Problem
You are given the heads of two sorted linked lists list1 and list2. Splice them together into one sorted list and return the head of the merged list.
Constraints
0 <= n1 + n2 <= 5000-100 <= Node.val <= 100Both inputs sorted ascending
Examples
Example 1
Input
list1 = [1,2,4], list2 = [1,3,4]Output
[1,1,2,3,4,4]Example 2
Input
list1 = [], list2 = [0]Output
[0]Approaches
1. Collect and sort
Push everything into an array, sort, rebuild.
- Time
- O((n+m) log(n+m))
- Space
- O(n+m)
const vals = [];
while (l1) { vals.push(l1.val); l1 = l1.next; }
while (l2) { vals.push(l2.val); l2 = l2.next; }
vals.sort((a,b) => a-b);Tradeoff:
2. Two-pointer splice
Dummy node + tail; attach smaller head at each step.
- Time
- O(n+m)
- Space
- O(1)
function merge(l1, l2) {
const dummy = { next: null }; 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;
return dummy.next;
}Tradeoff:
Coursera-specific tips
Coursera interviewers frame this as merging two sorted recommendation streams (e.g. relevance-ranked vs. recency-ranked course feeds) — call that out and show you can keep it O(1) extra space.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.