Merge Two Sorted Lists
Asked at Amazon, Microsoft, Adobe, Oracle, Rippling
Problem
Merge two sorted linked lists into one sorted list. This is a foundational linked list problem that appears frequently as a warm-up or follow-up question in FAANG interviews.
Asked At
| Company | Difficulty | |
|---|---|---|
| Amazon | Easy | View all Amazon questions → |
| Microsoft | Easy | View all Microsoft questions → |
| Adobe | Easy | View all Adobe questions → |
| Oracle | Easy | View all Oracle questions → |
| Rippling | Easy | View all Rippling questions → |
How to Think About It
Use a dummy head node to avoid special-casing the first node. The dummy's next pointer always points to the result. Return dummy.next at the end.
Compare the heads of both lists. The smaller node goes next in the result. Advance that list's pointer. Repeat until one list is exhausted.
When one list runs out, the other list still has nodes. Attach the remainder directly — it's already sorted.
Visual walkthrough for l1: 1→3→5, l2: 2→4→6:
Compare 1 vs 2: 1 smaller. Result: 1. l1 moves to 3.
Compare 3 vs 2: 2 smaller. Result: 1→2. l2 moves to 4.
Compare 3 vs 4: 3 smaller. Result: 1→2→3. l1 moves to 5.
Compare 5 vs 4: 4 smaller. Result: 1→2→3→4. l2 moves to 6.
Compare 5 vs 6: 5 smaller. Result: 1→2→3→4→5. l1 done.
Attach remainder: 1→2→3→4→5→6.
Recursive approach: if l1.val <= l2.val, l1.next = merge(l1.next, l2). Else l2.next = merge(l1, l2.next). Elegant but O(m+n) stack space.
Optimal Approach
Step 1: Create dummy head and tail pointer.
Step 2: While both lists have nodes:
- Compare l1.val and l2.val
- Attach the smaller node to tail
- Advance that list's pointer
- Advance tail
Step 3: Attach the remainder (l1 or l2, whichever is non-null).
Step 4: Return dummy.next.
The dummy head eliminates the "is this the first node?" check. Every node is appended the same way.
Time: O(m + n). Space: O(1) iterative, O(m + n) recursive.
What Trips People Up in Real Interviews
Creating a new list instead of modifying the existing ones. The problem says you can modify the input lists. Use the existing nodes to save space.
Forgetting to append the remaining list. After the main loop, one list might still have elements. Append the rest of the non-empty list.
Not handling empty lists. If one list is null, return the other. If both are null, return null.
Confusing "merge" with "concatenate." Merging interleaves elements in sorted order, not appends one list after the other.
Not handling the case where both lists have equal values. When l1.val == l2.val, either choice works, but you must advance one pointer — don't skip both or advance neither.
Solution Code
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def mergeTwoLists(l1, l2):
dummy = ListNode()
tail = dummy
while l1 and 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 or l2
return dummy.nextFrequently Asked Questions
What is the Merge Two Sorted Lists problem?
Merge two sorted linked lists into one sorted list. This is a foundational linked list problem that appears frequently as a warm-up or follow-up question in FAANG interviews.
How do you solve Merge Two Sorted Lists?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Merge Two Sorted Lists?
Merge Two Sorted Lists is asked at Amazon, Microsoft, Adobe, Oracle, Rippling. It is a easy difficulty problem.
What are common mistakes on Merge Two Sorted Lists?
- Creating a new list instead of modifying the existing ones. The problem says you can modify the input lists. Use the existing nodes to save space.
- Forgetting to append the remaining list. After the main loop, one list might still have elements. Append the rest of the non-empty list.
- Not handling empty lists. If one list is `null`, return the other. If both are `null`, return `null`.
- Confusing "merge" with "concatenate." Merging interleaves elements in sorted order, not appends one list after the other.
- Not handling the case where both lists have equal values. When l1.val == l2.val, either choice works, but you must advance one pointer — don't skip both or advance neither.