Merge Two Sorted Lists

Given the heads of two sorted singly linked lists, merge them into one sorted list. The machine must splice the two chains together by rewriting next pointers — it never allocates new nodes, it just relinks existing ones.

The key insight: rather than special-casing the empty-result head, use a dummy node as a sentinel. The result pointer stays fixed at the dummy while a tail pointer walks forward, so the merge loop body stays identical for the first element and every subsequent element.

Approach:

1. Create dummy = ListNode(0) and point tail at it.
2. While both lists are non-empty, attach the smaller head to tail.next and advance that list.
3. When one list empties, attach the remainder of the other wholesale — it is already sorted.

def merge_two_lists(l1, l2):
    dummy = tail = ListNode(0)
    while l1 and l2:
        if l1.val <= l2.val:
            tail.next, l1 = l1, l1.next
        else:
            tail.next, l2 = l2, l2.next
        tail = tail.next
    tail.next = l1 or l2
    return dummy.next

Time: O(n + m), every node visited once. Space: O(1) besides the dummy.

Trickiest edge case: one list empty from the start — the loop never runs and tail.next = l1 or l2 handles it, which is why the final attachment must be outside the loop.