Merge Two Sorted Linked Lists

Idea of the algorithm is:

1) Create a new link list list3 and save its head

2) Iterate over list1 and list2 and get the smallest element between the two current elements

3) Add this smallest element to list3 and incremente the pointer of the list where it comes from

4) Return the head of list3

def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
    list3 = ListNode()
    head = list3

    while list1 or list2:
        # if no element remains in list1 or if current val of list 2 is smaller than current val of list1 add list2 current node
        if not list1 or (list2 and list1.val > list2.val):
            list3.next = list2
            list2, list3 = list2.next, list3.next
        # otherwise add list1 current node
        else:
            list3.next = list1
            list1, list3 = list1.next, list3.next
            
    list3.next = None
    return(head.next)