3. Merge Two Sorted Lists
easyAsked at TeslaMerge two sorted linked lists into one sorted list.
By Sam K., Founder, InterviewChamp.AI · Last verified
Problem
You are given two sorted linked lists l1 and l2. Splice them into one sorted list and return the head. The result must reuse the original nodes.
Constraints
0 <= total nodes <= 100-100 <= node.val <= 100Inputs are sorted ascending
Examples
Example 1
Input
l1 = [1,2,4], l2 = [1,3,4]Output
[1,1,2,3,4,4]Example 2
Input
l1 = [], l2 = [0]Output
[0]Approaches
1. Collect and re-sort
Dump values into an array, sort, rebuild list.
- Time
- O(n log n)
- Space
- O(n)
const vals = [];
for (let p of [l1,l2]) while (p) { vals.push(p.val); p = p.next; }
vals.sort((a,b)=>a-b);
// rebuild...Tradeoff:
2. Dummy head merge
Walk both lists with a tail pointer attached to a dummy. Splice the smaller head 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:
Tesla-specific tips
Tesla likes pointer-clean merges — they're the linked-list analog of fusing two sensor streams into one timestamp-sorted feed and the in-place version avoids heap allocations in the hot path.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.