Approach Summary
Use a dummy head node. Compare heads of both lists, advance the smaller one. Attach remaining list at the end.
Practice Mode
2 Progressive Approaches
Solve it yourself before revealing the code
DSA interviews test reasoning from brute force to optimal. Think through the constraints first.
Solution Progression (Brute Force → Most Optimized)
Understand the architectural evolution from naive baseline to optimal complexity.
| Approach | Time | Space | Core Strategy / Trade-off |
|---|---|---|---|
| 1 Approach 1: Recursive Merge | O(m + n) | O(m + n) call stack | Recursively attach the smaller node and merge the remaining sublists. |
| 2 Approach 2: In-Place Iterative Splice (Optimal) | O(m + n) | O(1) | Splice nodes in-place using pointer swapping without extra node allocations in O(1) space. |
Step 1: Baseline
Approach 1: Recursive Merge
Time: O(m + n)
Space: O(m + n) call stack
If either list is null, return the other list. Otherwise, compare list1.val and list2.val: attach the smaller node's next to the recursive call of mergeTwoLists on its successor and the other list.
Approach 1: Recursive Merge Implementation
Approach 1: Recursive Merge
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
if (list1 == null) return list2;
if (list2 == null) return list1;
if (list1.val <= list2.val) {
list1.next = mergeTwoLists(list1.next, list2);
return list1;
} else {
list2.next = mergeTwoLists(list1, list2.next);
return list2;
}
}
}class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
if (list1 == NULL) return list2;
if (list2 == NULL) return list1;
if (list1->val <= list2->val) {
list1->next = mergeTwoLists(list1->next, list2);
return list1;
} else {
list2->next = mergeTwoLists(list1, list2->next);
return list2;
}
}
};class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
if not list1:
return list2
if not list2:
return list1
if list1.val <= list2.val:
list1.next = self.mergeTwoLists(list1.next, list2)
return list1
else:
list2.next = self.mergeTwoLists(list1, list2.next)
return list2function mergeTwoLists(list1, list2) {
if (!list1) return list2;
if (!list2) return list1;
if (list1.val <= list2.val) {
list1.next = mergeTwoLists(list1.next, list2);
return list1;
} else {
list2.next = mergeTwoLists(list1, list2.next);
return list2;
}
} Step 2: Most Optimized
Approach 2: In-Place Iterative Splice (Optimal)
Time: O(m + n)
Space: O(1)
Ensure list1 starts at the smaller value. While both lists are non-empty, advance list1 through contiguous nodes that are <= list2.val. Once list1 encounters a larger value, point the previous node to list2 and swap the pointers so list1 always refers to the active smaller chain.
Approach 2: In-Place Iterative Splice (Optimal) Implementation
Approach 2: In-Place Iterative Splice (Optimal)
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
if (list1 == null) return list2;
if (list2 == null) return list1;
if (list1.val > list2.val) {
ListNode temp = list1; list1 = list2; list2 = temp;
}
ListNode result = list1;
while (list1 != null && list2 != null) {
ListNode temp = null;
while (list1 != null && list1.val <= list2.val) {
temp = list1;
list1 = list1.next;
}
temp.next = list2;
ListNode tmp = list1; list1 = list2; list2 = tmp;
}
return result;
}
}class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
if (!list1) return list2;
if (!list2) return list1;
if (list1->val > list2->val) swap(list1, list2);
ListNode* result = list1;
while (list1 != NULL && list2 != NULL) {
ListNode* temp = NULL;
while (list1 != NULL && list1->val <= list2->val) {
temp = list1;
list1 = list1->next;
}
temp->next = list2;
swap(list1, list2);
}
return result;
}
};class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode(0)
tail = dummy
while list1 and list2:
if list1.val <= list2.val:
tail.next = list1
list1 = list1.next
else:
tail.next = list2
list2 = list2.next
tail = tail.next
tail.next = list1 or list2
return dummy.nextfunction mergeTwoLists(list1, list2) {
const dummy = new ListNode(0);
let tail = dummy;
while (list1 && list2) {
if (list1.val <= list2.val) {
tail.next = list1;
list1 = list1.next;
} else {
tail.next = list2;
list2 = list2.next;
}
tail = tail.next;
}
tail.next = list1 || list2;
return dummy.next;
}Edge Cases to Watch
- Both lists are empty (returns null)
- One list is empty (returns the other list)
- Lists of different lengths (e.g. length 1 and length 10)
- Lists with duplicate or identical values
Algorithmic Pattern
View Pattern Guide →
Master the Linked List Pattern
Study the core invariant, step-by-step decision framework, and common interview traps for the Linked List pattern.
Framework: Linked List • Interview Prep: Tested at FAANG •
Explore all Linked List problems & invariants →
How to Recognize This Pattern
- Merge two sorted sequences
- Dummy head pattern
Complexity Analysis
Time Complexity
O(n + m)
Space Complexity
O(1)
Tags
Linked List Recursion
Frequently Asked Questions
What is the optimal time and space complexity for Merge Two Sorted Lists?
The optimal solution for Merge Two Sorted Lists achieves O(n + m) runtime complexity and requires O(1) auxiliary space. Time complexity is O(m + n) where m and n are lengths of the lists because each node is attached to the merged list once. Space complexity is O(1) for the iterative pointer splice and O(m + n) for the recursive call stack.
How do I identify that Merge Two Sorted Lists requires the Linked List pattern?
In technical interviews, look for key problem signals: Merge two sorted sequences; Dummy head pattern. Recognizing these invariants allows you to bypass naive brute-force exhaustive search in favor of Linked List strategy.
What critical edge cases must be handled in Merge Two Sorted Lists?
Essential edge cases to verify include: Both lists are empty (returns null); One list is empty (returns the other list); Lists of different lengths (e.g. length 1 and length 10); Lists with duplicate or identical values. Always walk through these scenarios with your interviewer before coding.
Which tech companies frequently ask Merge Two Sorted Lists?
Merge Two Sorted Lists is a Easy-difficulty question tagged with high recurrence. It is actively asked in technical screening and onsite interview loops at Amazon, Microsoft, Apple.