3. Merge Two Sorted Lists
easyAsked at SlackMerge two sorted singly 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 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 non-decreasing
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. Collect and sort
Copy all values into an array, sort, rebuild.
- 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);
// rebuild listTradeoff:
2. Two-pointer splice
Use a dummy head and a tail pointer. Pick the smaller head each step. Append leftover.
- 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:
Slack-specific tips
Slack's message-history merge (across reconnects) is a real-world variant — mention how you'd merge two ordered message streams by ts.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.