Merge Two Sorted Lists

easyTests passed 2026-11-11v1.0.0

TC: O(N + M)|SC: O(1)

Linked Lists Original Statement (leetcode).md

1. Core Invariant / The Trick

Anchor the output with a `dummy` sentinel node and a `tail` pointer. Repeatedly attach the smaller of `l1` and `l2`, then splice whichever tail remains non-null in O(1).

2. Complexity Bounds & Proof

Each comparison advances one pointer until at least one list finishes; existing nodes are relinked in place.

3. Minimal Idiomatic Code

def mergeTwoLists(l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
    dummy = tail = ListNode()
    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

4. Failure Modes & Interview Follow-ups

Pitfalls:- Writing separate head initialization logic causes null-pointer edge bugs on empty inputs. - Iterating instead of splicing the remaining non-null list wastes loop iterations.

Follow-ups:- Generalizes directly to Merge k Sorted Lists via min-heap or divide-and-conquer pairwise merging.

Personal Notes & Scratchpad (Local-First Yjs CRDT)

Saved instantaneously in IndexedDB. Streams live across peers via Hocuspocus when signed in.

Related Invariants

Merge k Sorted Lists (O(N log k))

Browser Scratchpad

Console Output

Click Run or press Cmd/Ctrl+Enter to execute locally in a Web Worker.