lets first understand the question
Given two sorted linked lists list1 and list2, merge them into one sorted linked list and return the head of the merged list
sample i/p and o/p from a question
Input:
list1 = [1,2,4]
list2 = [1,3,4]
Output:
[1,1,2,3,4,4]
Explanation: both lists are already sorted, so we merge them in such a way that the final list is also sorted
how to approach the solution
I started with a question "How do I compare two linked lists element by element?"
since the lists are already sorted, we don’t need to sort again
so the idea is simple → compare elements and take the smaller one
how it works
let the given lists be
list1 = 1 → 2 → 4
list2 = 1 → 3 → 4
we compare both nodes step by step
1 vs 1 → take 1
2 vs 1 → take 1
2 vs 3 → take 2
4 vs 3 → take 3
4 vs 4 → take 4
remaining → 4
so the final list becomes
1 → 1 → 2 → 3 → 4 → 4
Approach
we use a dummy node to make linking easy
current pointer is used to build the new list
compare both lists
attach smaller node
move that list forward
at the end, attach remaining elements
Algorithm
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def mergeTwoLists(list1, list2):
dummy = ListNode(-1)
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
if list1:
current.next = list1
else:
current.next = list2
return dummy.next