Merge Two Sorted Lists

Free with account Updated Nov 19, 2026 · 4 min read
On this page

    Problem statement

    Given the heads of two sorted singly linked lists, merge them into one sorted list by splicing their nodes together, and return its head. Reuse the existing nodes; either list may be empty.

    It's the merge step of merge sort on linked lists, and the base case of Merge k Sorted Lists. The clean solution uses a dummy node so the head isn't a special case. Original problem: LeetCode 21.

    Example

    Merging 1 → 2 → 4 with 1 → 3 → 4 interleaves their nodes into 1 → 1 → 2 → 3 → 4 → 4.
    Merging 1 → 2 → 4 with 1 → 3 → 4 interleaves their nodes into 1 → 1 → 2 → 3 → 4 → 4.
    Input:  1 -> 2 -> 4,  1 -> 3 -> 4
    Output: 1 -> 1 -> 2 -> 3 -> 4 -> 4
    Input:  null,  0
    Output: 0

    Constraints (assumed)

    • 0 ≤ nodes in each list ≤ 50.
    • Values between −100 and 100; both lists sorted ascending.

    What this question tests

    • The two-pointer merge on linked lists.
    • Using a dummy head to avoid special-casing the first node.
    • Not forgetting the leftover part of the longer list.

    Questions to ask first

    1. Can I reuse the input nodes? (Here: yes; splice, don't copy.)
    2. Sorted ascending, with duplicates allowed? (Yes.)
    3. Should the merge be stable (equal values from list1 first)? Using ≤ gives that.
    4. Iterative or recursive? Either; recursion uses O(n + m) stack.