21. Merge Two Sorted Lists ¶ Time: $O(|\texttt{list1}| + |\texttt{list2}|))$ Space: $O(1)$ C++JavaPython 1 2 3 4 5 6 7 8 9 10 11class 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; } }; 1 2 3 4 5 6 7 8 9 10 11 12 13class 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; } } 1 2 3 4 5 6 7 8class 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