LeetCode Solutions
21. Merge Two Sorted Lists
Time: $O(|\texttt{list1}| + |\texttt{list2}|))$ Space: $O(|\texttt{list1}| + |\texttt{list2}|))$
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
if (!list1 || !list2)
return list1 ? list1 : list2;
if (list1->val > list2->val)
swap(list1, list2);
list1->next = mergeTwoLists(list1->next, list2);
return list1;
}
};
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
if (list1 == null || list2 == null)
return list1 == null ? list2 : list1;
if (list1.val > list2.val) {
ListNode temp = list1;
list1 = list2;
list2 = temp;
}
list1.next = mergeTwoLists(list1.next, list2);
return list1;
}
}
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
if not list1 or not list2:
return list1 if list1 else list2
if list1.val > list2.val:
list1, list2 = list2, list1
list1.next = self.mergeTwoLists(list1.next, list2)
return list1