Loading…
Merge Two Sorted Lists is a easy coding interview question covering linked list, recursion — the kind asked at FAANG (Facebook/Meta, Apple, Amazon, Netflix, Google) and AI-first companies like Anthropic, OpenAI, and Nvidia.
Merge two sorted linked lists and return the merged list as a sorted linked list.
Example: 1→2→4 merged with 1→3→4 gives 1→1→2→3→4→4
Try it yourself first
In an interview you'd get about 15 minutes for a easy question. Sketch an approach before peeking — struggling is where the learning happens.
Stuck? Reveal them one at a time — each hint gives away a little more.
Ready to compare notes? The full solution, visualization, and complexity analysis are below.
L1 → 1 → 2 → 4 → null
L2 → 1 → 3 → 4 → null
Result (building)
Variables
| 1 | def merge_two_lists(l1, l2): |
| ▶ | dummy = ListNode(0) |
| ▶ | curr = dummy |
| 4 | while l1 and l2: |
| 5 | if l1.val <= l2.val: |
| 6 | curr.next = l1 |
| 7 | l1 = l1.next |
| 8 | else: |
| 9 | curr.next = l2 |
| 10 | l2 = l2.next |
| 11 | curr = curr.next |
| 12 | curr.next = l1 or l2 |
| 13 | return dummy.next |
Create a dummy head node and curr pointer. The dummy node lets us avoid special-casing an empty result list.
Time
O(n + m)
Space
O(1)
Collect every value into an array, sort it, rebuild the list
O((n + m) log(n + m)) time, O(n + m) space
It ignores the premise. Both inputs are already sorted, which is precisely the information that makes a linear merge possible - re-sorting pays for order you were handed for free.
Recursive merge
O(n + m) time, O(n + m) space
The most elegant version of this solution, and the one that breaks in production: recursion depth grows with the combined length, so long lists overflow the stack. Say it, then write the iterative one.
Iterative: use a dummy head node. Compare the heads of both lists, append the smaller to the result, advance that list's pointer. Append any remaining nodes. O(n+m) time.
A full interview loop is more than one round. These are the others, each with what is on the site for it.