3. Merge Two Sorted Lists
easyAsked at MercadoLibreMerge 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 them into one sorted list by splicing together the nodes of the first two lists. Return the head of the merged list.
Constraints
0 <= list length <= 50-100 <= node value <= 100Both lists are 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. Brute force
Collect values to an array, sort, rebuild list.
- 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
Walk both lists with a dummy head, picking the smaller node 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:
MercadoLibre-specific tips
MercadoLibre uses this to confirm dummy-node and pointer hygiene, which matter for their search-result merge pipelines combining multiple ranked sources.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.