Merge two sorted lists

python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        cur = dummy = ListNode()
        while list1 and list2:
            if list1.val < list2.val:
                cur.next = list1
                list1 = list1.next
            else:
                cur.next = list2
                list2 = list2.next
            cur = cur.next
        cur.next = list1 or list2 # merge the leftover linklist
        return dummy.next

if list1 or list2 is None, then the leftover must be larger than the tail of new linked list. So we just concatenate the leftovers.

Create a dummy node to contain a new linked list. Then compare the value of two linked lists, to decide the next node.

Remember to connect the leftover list.