Merge Two Sorted Lists

👶 The 5-Year-Old Summary

You have two lines of kids sorted by height. Merge them into one line that's still sorted! Compare the first kid from each line, put the shorter one first, repeat.

🎮 Interactive Visualizer

List 1: 1 → 2 → 4

List 2: 1 → 3 → 4

Result:

🧠 The Brain Hack

Use a dummy node! It simplifies the code by handling the head without special cases. Compare l1 vs l2, pick smaller, attach to dummy's tail!

💻 The Clean Solution

def merge_two_lists(l1, l2):
    # Dummy node - acts as placeholder for result head
    dummy = ListNode(0)
    tail = dummy
    
    # Compare and pick the smaller node
    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
    
    # Attach remaining nodes
    tail.next = l1 or l2
    
    return dummy.next

Time: O(n + m)

Space: O(1)