3. Merge Two Sorted Lists
easyAsked at QuoraMerge two sorted linked lists into one sorted list.
By Sam K., Founder, InterviewChamp.AI · Last verified
Problem
You are given the heads of two sorted linked lists list1 and list2. Merge the two lists into one sorted list by splicing nodes together. Return the head of the merged list.
Constraints
0 <= total nodes <= 50-100 <= Node.val <= 100Both lists sorted non-decreasing
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
Dump all values into an array and sort.
- Time
- O(n log n)
- Space
- O(n)
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);
// rebuild listTradeoff:
2. Two-pointer splice
Walk both heads with a dummy node and pick the smaller value 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:
Quora-specific tips
Quora reaches for merge-sorted patterns because their answer-feed merges ranked streams from followed topics, followed users, and recency in real time.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.