3. Merge Two Sorted Lists
easyAsked at CheggSplice two sorted linked lists into one — Chegg uses this to check pointer hygiene on ordered tutor-availability merges.
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. Return the head of the merged linked list.
Constraints
0 <= number of nodes <= 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 = []Output
[]Approaches
1. Recursive
Pick smaller head, recurse on the rest.
- Time
- O(n+m)
- Space
- O(n+m)
function merge(a, b) {
if (!a || !b) return a || b;
if (a.val < b.val) { a.next = merge(a.next, b); return a; }
b.next = merge(a, b.next); return b;
}Tradeoff:
2. Iterative dummy node
Walk both lists, attach the smaller head to a dummy tail. O(1) extra space beyond the merged list.
- Time
- O(n+m)
- Space
- O(1)
function mergeTwoLists(a, b) {
const dummy = { next: null };
let tail = dummy;
while (a && b) {
if (a.val < b.val) { tail.next = a; a = a.next; }
else { tail.next = b; b = b.next; }
tail = tail.next;
}
tail.next = a || b;
return dummy.next;
}Tradeoff:
Chegg-specific tips
Chegg interviewers prefer the iterative dummy-node solution because it mirrors how their tutor-matching service streams sorted availability windows without per-call allocations.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.