3. Merge Two Sorted Lists
easyAsked at GlassdoorMerge two sorted linked lists into one sorted list — Glassdoor uses this to test pointer hygiene under interleaved inputs.
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. The list should be made by splicing together the nodes of the first two lists.
Constraints
0 <= each list length <= 50-100 <= node.val <= 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 = []Output
[]Approaches
1. Collect and sort
Dump both lists into an array and sort.
- Time
- O((m+n) log(m+n))
- Space
- O(m+n)
const arr = [];
for (let n=l1; n; n=n.next) arr.push(n.val);
for (let n=l2; n; n=n.next) arr.push(n.val);
arr.sort((a,b)=>a-b);
// rebuild list from arrTradeoff:
2. Two-pointer splice
Walk both lists with a dummy head and splice the smaller node.
- Time
- O(m+n)
- 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:
Glassdoor-specific tips
Glassdoor likes the dummy-head pattern called out explicitly — their review-merge pipelines use the same sentinel trick to avoid null edge-cases.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.