3. Merge Two Sorted Lists
easyAsked at LINEMerge two sorted linked lists into one sorted list — LINE uses this as a proxy for merging two ordered chat timelines.
By Sam K., Founder, InterviewChamp.AI · Last verified
Problem
You are given the heads of two sorted linked lists. Splice them together into one sorted linked list by reusing nodes (no new node creation), and return the new head.
Constraints
0 <= list length <= 50-100 <= Node.val <= 100Both lists are sorted non-decreasing.
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 sort
Push all values into an array, sort, then rebuild a linked list.
- Time
- O((m+n) log (m+n))
- Space
- O(m+n)
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 pointers with dummy head
Walk both lists with two pointers, attach the smaller node, advance, then append the tail.
- Time
- O(m+n)
- Space
- O(1)
function mergeTwoLists(l1, l2) {
const dummy = { val: 0, 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:
LINE-specific tips
Frame this as merging two device-side chat-history pages during sync — LINE engineers do exactly this when a phone reconnects after offline.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.