How to Solve Merge Two Sorted Linked Lists on LeetCode
The Merge Two Sorted Linked Lists problem is a core LeetCode and interview question testing your understanding of pointer manipulation and recursive problem solving.
Problem Statement
Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists.
Example:
Input: l1 = [1,2,4], l2 = [1,3,4]
Output: [1,1,2,3,4,4]
Why This Problem Matters for Interviews
This problem:
- Assesses your pointer handling skills
- Tests both recursive and iterative thinking
- Is a common subroutine for harder linked list problems
Approaches to Merge Two Sorted Linked Lists
1. Iterative Approach
Walk through both lists, attach smaller node to result.
Time Complexity: O(n + m)
Space Complexity: O(1)
def mergeTwoLists(l1, l2):
dummy = curr = ListNode(0)
while l1 and l2:
if l1.val < l2.val:
curr.next, l1 = l1, l1.next
else:
curr.next, l2 = l2, l2.next
curr = curr.next
curr.next = l1 or l2
return dummy.next
2. Recursive Approach
Return the smaller head, then merge the rest.
Time Complexity: O(n + m)
Space Complexity: O(n + m) for recursion stack
def mergeTwoLists(l1, l2):
if not l1 or not l2:
return l1 or l2
if l1.val < l2.val:
l1.next = mergeTwoLists(l1.next, l2)
return l1
else:
l2.next = mergeTwoLists(l1, l2.next)
return l2
Key Interview Talking Points
- Compare iterative vs recursive approach and stack space
- Handling empty lists and duplicates
- Why this merge is stable
- How this is used in merge sort
Big O Complexity Recap
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Iterative | O(n + m) | O(1) |
| Recursive | O(n + m) | O(n + m) |
Pro Interview Tips
- Explain pointer manipulation in detail.
- Mention edge cases with empty or single-element lists.
- Practice with test cases