Merge a Pair of Ascending Linked Lists Recursively

Easy15–20 min

Topics

RecursionLinked ListTwo Pointers

Companies

AmazonMicrosoftApple

Given two sorted linked lists list1 and list2, merge them into a single sorted linked list by splicing the existing nodes together — no new nodes should be created. The recursive framing turns the merge into a chain of small decisions: compare the two current heads, let the smaller one lead, and set its `next` pointer to the result of recursively merging everything after it with the other list untouched. The base cases are immediate — merging anything with an empty list is just that list, unchanged. Every call makes exactly one decision and hands off a strictly smaller version of the same problem, so the total number of calls (and the total work) is proportional to the combined length of both lists — the same O(n+m) as the iterative two-pointer approach, just paying for it in call-stack frames instead of a fixed pair of pointers.

Test Case 1:

Input:list1 = [2, 6, 9], list2 = [1, 6, 8, 12]

Output:[1, 2, 6, 6, 8, 9, 12]

Explanation:Every node from both lists, interleaved so the result stays sorted. Equal values (both 6's) keep list1's node first, since the comparison uses ≤.

Test Case 2:

Input:list1 = [], list2 = [5, 7]

Output:[5, 7]

Explanation:An empty list1 means the result is exactly list2.

Test Case 3:

Input:list1 = [3], list2 = []

Output:[3]

Explanation:An empty list2 means the result is exactly list1.

Constraints

◆0 ≤ number of nodes in list1, list2 ≤ 10 each
◆-100 ≤ node value ≤ 100
◆Both list1 and list2 are sorted in non-decreasing order

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Iterative — Two Pointers, Splice Nodes In Place

Optimal

Walk both lists together with two pointers. At every step, whichever current node holds the smaller value gets spliced onto the end of the result, and that list's pointer advances. No new nodes are created — existing ones are simply re-linked. Once one list runs out, the other's remaining nodes are already sorted, so the whole remainder attaches in one shot. This uses no extra memory beyond a couple of pointers, regardless of how long either list is.

TimeO(n + m)

SpaceO(1)

Java

Try it out

class Solution {
    public Node mergeTwoSortedListsRecursive(Node list1, Node list2) {
        Node dummy = new Node(0);
        Node tail = dummy;
        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                tail.next = list1;
                list1 = list1.next;
            } else {
                tail.next = list2;
                list2 = list2.next;
            }
            tail = tail.next;
        }
        tail.next = (list1 != null) ? list1 : list2;
        return dummy.next;
    }
}

Recursive — Whichever Head Is Smaller Leads

Good

Compare the two current heads: whichever is smaller becomes the first node of the merged result, and its `next` pointer is set to the merged result of *the rest of its own list* combined with *all of the other list* — a smaller version of the exact same problem. The base cases are simple: merging anything with an empty list is just that non-empty list, unchanged. Every call picks exactly one node and recurses on what's left, so the total number of calls is proportional to the combined length of both lists.