3. Merge Two Sorted Lists
easyAsked at ByteDanceStitch two sorted linked lists into one — ByteDance uses this to test pointer hygiene that maps directly to merging sorted candidate rankings.
By Sam K., Founder, InterviewChamp.AI · Last verified
Problem
You are given the heads of two sorted linked lists. Merge them into one sorted list by splicing nodes together and return the new head.
Constraints
The number of nodes in both lists is in [0, 50]-100 <= Node.val <= 100Both lists are sorted in non-decreasing order
Examples
Example 1
Input
l1 = [1,2,4], l2 = [1,3,4]Output
[1,1,2,3,4,4]Example 2
Input
l1 = [], l2 = []Output
[]Approaches
1. Brute force collect-and-sort
Copy values to array, sort, rebuild list.
- 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 list from valsTradeoff:
2. Two-pointer splice
Use a dummy head and advance whichever list has the smaller current value.
- 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:
ByteDance-specific tips
ByteDance grades for clean dummy-head usage and no node leakage — they explicitly probe whether you'd reuse this in a candidate-merge step at TikTok scale.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.