EACH LIST IS ALREADY SORTED, SO THE NEXT SMALLEST VALUE IS ALWAYS ONE OF THE TWO HEADS. COMPARE THEM, TAKE THE SMALLER, REPEAT. A DUMMY NODE GIVES THE TAIL SOMETHING TO POINT AT BEFORE THE FIRST SPLICE.

BLUE L1 AND MAGENTA L2 MARK THE TWO HEADS. THE SMALLER IS SPLICED ONTO THE TAN RESULT CHAIN AND GREEN TAIL FOLLOWS. WHEN ONE LIST EMPTIES, ATTACH THE REST. THE GOLD TILE IS THE RETURNED HEAD.

1def mergeTwoLists(list1, list2):2    dummy = ListNode()3    tail = dummy4    while list1 and list2:5        if list1.val < list2.val:6            tail.next = list17            list1 = list1.next8        else:9            tail.next = list210            list2 = list2.next11        tail = tail.next12    tail.next = list1 or list213    return dummy.next