Merge Two Sorted Lists

Intuition

Because both inputs are already sorted, the next node in the merged output is always whichever front node is smaller. That observation turns the problem into a simple linear scan with two pointers. A dummy head removes the awkwardness of choosing and initializing the very first node: we just keep a tail pointer and splice nodes onto it. Each comparison advances exactly one input pointer, so no nodes are ever revisited. When one list runs out, everything remaining in the other list is already sorted and larger, so we attach it wholesale.

Algorithm walkthrough

1. 1Create a dummy node and a tail pointer that starts at the dummy.
2. 2While both lists still have nodes, compare their head values.
3. 3Attach the node with the smaller value to tail.next and advance that list's pointer.
4. 4Advance the tail pointer to the node just attached.
5. 5Once the loop ends, at most one list is non-empty; attach it directly to tail.next.
6. 6Return dummy.next as the head of the merged list.

Implementation

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0)
        tail = dummy
        while list1 and list2:
            if list1.val <= list2.val:
                tail.next = list1
                list1 = list1.next
            else:
                tail.next = list2
                list2 = list2.next
            tail = tail.next
        tail.next = list1 if list1 else list2
        return dummy.next