Merge Two Sorted Lists

Problem page:https://leetcode.com/problems/merge-two-sorted-lists

Solution

def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        sentinel = ListNode()
        cur = sentinel
        while list1 and list2:
            if list1.val > list2.val:
                cur.next = list2
                list2 = list2.next
            else:
                cur.next = list1
                list1 = list1.next
            cur = cur.next
        if list1:
            cur.next = list1
        else:
            cur.next = list2
        return sentinel.next

Complexity

• time: O(m + n)
• space: O(1)