🎨Now live: Try our Free AI Image Generation Feature

Intuition
To merge two sorted linked lists into one sorted list, we can utilize a pointer-based approach. Given that both list1
and list2
are already sorted, merging them involves comparing nodes from both lists and linking them in ascending order.
Approach
- Initialization: Start with two pointers,
merged_head
andcurrent
, both initialized toNone
. - Comparative Merging: Compare the values of the heads of
list1
andlist2
. Setmerged_head
to the smaller node, and move the respective list's pointer forward. - Iterative Merging: Continue comparing the current nodes of
list1
andlist2
. Link the smaller node tocurrent.next
, and movecurrent
and the pointer of the smaller node forward. - Append Remaining Nodes: Once one list is exhausted, append the remaining nodes of the other list directly to
current.next
. - Return: Return
merged_head
, which now points to the head of the merged sorted list.
Complexity
Time Complexity:
O(m + n), where m and n are the lengths of list1
and list2
, respectively. We iterate through both lists once.
Space Complexity**:
O(1), since we only use a constant amount of extra space for pointers and variables, not proportional to the input size.
Code
C++
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* 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;
}
}
};
Python
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:
merged_head = list1
list1 = list1.next
else:
merged_head = list2
list2 = list2.next
current = merged_head
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
elif list2:
current.next = list2
return merged_head
Java
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;
}
}
}
JavaScript
var mergeTwoLists = function (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;
}
};