21. Merge Two Sorted Lists

 1# Definition for singly-linked list.
 2# class ListNode:
 3#     def __init__(self, val=0, next=None):
 4#         self.val = val
 5#         self.next = next
 6class Solution:
 7    def mergeTwoLists(
 8        self, list1: Optional[ListNode], list2: Optional[ListNode]
 9    ) -> Optional[ListNode]:
10        if not list1 and not list2:
11            return None
12        elif not list1:
13            return list2
14        elif not list2:
15            return list1
16
17        head = None
18        if list1.val <= list2.val:
19            head = list1
20            list1 = list1.next
21        else:
22            head = list2
23            list2 = list2.next
24
25        node = head
26
27        while True:
28            nxt = None
29            if list1 and list2:
30                if list1.val <= list2.val:
31                    nxt = list1
32                    list1 = list1.next
33                else:
34                    nxt = list2
35                    list2 = list2.next
36            elif list1:
37                nxt = list1
38                list1 = list1.next
39            elif list2:
40                nxt = list2
41                list2 = list2.next
42            else:
43                break
44
45            node.next = nxt
46            node = nxt
47
48        return head