How I Understood Merge Two Sorted Lists (LeetCode 21)
When I first saw this problem, I thought it would be confusing because it involves linked lists.
But after trying it myself, I realized it's actually simple if you focus on one thing: comparison step by step.
Problem
We are given two sorted linked lists.
Example:
list1 = [1,2,4]
list2 = [1,3,4]
Expected output:
[1,1,2,3,4,4]
What I Noticed
Both lists are already sorted.
So instead of thinking about sorting again, I just focused on:
- Compare the current values
- Pick the smaller one
- Move forward
That’s the whole idea.
What Helped Me
Using a dummy node made things much easier.
Without it, I was confused about how to start the new list.
With it, I just kept adding nodes without worrying about the head.
Approach
- Create a dummy node
- Use a pointer to build the new list
- Compare nodes from both lists
- Attach the smaller node
- Move that list forward
- Continue until one list ends
- Attach the remaining part
Code (Python)
class Solution:
def mergeTwoLists(self, list1, list2):
dummy = ListNode(0)
current = dummy
while list1 and list2:
if list1.val < list2.val:
current.next = list1
list1 = list1.next
else:
current.next = list2
list2 = list2.next
current = current.next
current.next = list1 if list1 else list2
return dummy.next
Complexity
Time: O(n + m)
Space: O(1)
What I Learned
This problem is not about writing complex code.
It’s about:
- thinking clearly
- comparing values carefully
- moving step by step
Final Thought
At first, I felt this problem was tricky.
But once I broke it down into small steps, it became easy.
If you're stuck, just ask yourself:
“Which value is smaller right now?”
That’s enough to solve it.
Top comments (0)