3. Merge Two Sorted Lists
easyAsked at N26Merge two sorted linked lists into one sorted list. N26 uses this to probe pointer hygiene before scaling up to merging chronologically sorted multi-currency transaction streams.
By Sam K., Founder, InterviewChamp.AI · Last verified
Problem
Merge two sorted linked lists into one sorted list. The result should be spliced together from the nodes of the first two lists. Return the head of the merged list.
Constraints
0 <= list length <= 50-100 <= Node.val <= 100Both lists 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 resort
Flatten values into array, sort, rebuild list.
- Time
- O((n+m) log(n+m))
- Space
- O(n+m)
const arr = [];
while(l1){arr.push(l1.val);l1=l1.next;}
while(l2){arr.push(l2.val);l2=l2.next;}
arr.sort((a,b)=>a-b);Tradeoff:
2. Two-pointer splice
Walk both lists with a dummy head; attach the smaller node at each step.
- Time
- O(n+m)
- Space
- O(1)
function mergeTwoLists(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:
N26-specific tips
N26 graders reward you for naming the analogy to merging EUR and GBP transaction feeds during nightly settlement.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.