Dare2Solve
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.
merged_head
and current
, both initialized to None
.list1
and list2
. Set merged_head
to the smaller node, and move the respective list's pointer forward.list1
and list2
. Link the smaller node to current.next
, and move current
and the pointer of the smaller node forward.current.next
.merged_head
, which now points to the head of the merged sorted list.O(m + n), where m and n are the lengths of list1
and list2
, respectively. We iterate through both lists once.
O(1), since we only use a constant amount of extra space for pointers and variables, not proportional to the input size.
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;
}
}
};
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
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;
}
}
}
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;
}
};