A payments service holds two already-sorted queues: overnight ACH invoices and the same-day card batch, each a singly linked list ordered by invoice id. Finance wants one merged queue, still sorted, without allocating a third pile of invoice objects. The intern version walked both lists, dumped amounts into an ArrayList, sorted, and built a new chain. The numbers were right. The nodes were not. Every downstream job that still held a node from either source queue was looking at the old successor.

Merging two sorted singly linked lists means rewiring next pointers so one sorted chain uses the same nodes. The linked list post owns splice, dummy nodes, and why get(i) walks. Here we only care about a dummy head and always taking the smaller current node. Reverse already taught that copying values is not a reverse of the list you were given; the same identity rule applies here.

The problem

Given the heads of two sorted singly linked lists, merge them into one sorted list by rewiring the existing nodes. Return the new head. Either list may be empty.

a = 2 → 5 → 9
b = 3 → 5 → 8
merged = 2 → 3 → 5 → 5 → 8 → 9

a = empty
b = 4 → null
merged = 4 → null

a = empty
b = empty
merged = empty

A node is the usual two fields:

final class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
    }
}

Note: In-place means the same node objects, new next links. Dumping values into an ArrayList, sorting, and allocating a new chain passes a value-order test and fails any test that identity of nodes matters — or any follow-up that said O(1) extra space.

Copy, sort, rebuild is the honest brute

Walk both lists, collect every val, sort, then allocate a fresh chain. The numbers come out sorted. The objects are not the ones you were handed.

ListNode mergeByCopy(ListNode a, ListNode b) {
    List<Integer> vals = new ArrayList<>();
    for (ListNode n = a; n != null; n = n.next) {
        vals.add(n.val);
    }
    for (ListNode n = b; n != null; n = n.next) {
        vals.add(n.val);
    }
    Collections.sort(vals);
    if (vals.isEmpty()) {
        return null;
    }
    ListNode head = new ListNode(vals.get(0));
    ListNode tail = head;
    for (int i = 1; i < vals.size(); i++) {
        tail.next = new ListNode(vals.get(i));
        tail = tail.next;
    }
    return head;
}

At a handful of invoices this is a rounding error. In production you paid O((m + n) log (m + n)) extra time, O(m + n) extra nodes, and you threw away the objects callers still held. The lists were already sorted. You did not need a second sort.

Dummy head, then always splice the smaller node

A dummy head gives the first splice a predecessor, so empty and non-empty merges share the same loop. Keep tail on the last node of the merged prefix. Walk both inputs. Each step, splice the smaller current node onto tail, then advance that list and tail. When one list is exhausted, splice the leftover chain in one assignment.

Walk 2 → 5 → 9 against 3 → 5 → 8:

start: dummy → null,  tail=dummy,  a=2, b=3

2 vs 3: splice 2, a=5     dummy → 2
5 vs 3: splice 3, b=5     dummy → 2 → 3
5 vs 5: splice a, a=9     dummy → 2 → 3 → 5
9 vs 5: splice b, b=8     dummy → 2 → 3 → 5 → 5
9 vs 8: splice b, b=null  dummy → 2 → 3 → 5 → 5 → 8

remainder: tail.next = a   dummy → 2 → 3 → 5 → 5 → 8 → 9
return dummy.next

The Java is that walk:

ListNode mergeTwoLists(ListNode a, ListNode b) {
    ListNode dummy = new ListNode(0);
    ListNode tail = dummy;
    while (a != null && b != null) {
        if (a.val <= b.val) {
            tail.next = a;
            a = a.next;
        } else {
            tail.next = b;
            b = b.next;
        }
        tail = tail.next;
    }
    tail.next = (a != null) ? a : b;
    return dummy.next;
}

Time is O(m + n) — each node is visited once. Space is O(1) besides the dummy. The leftover splice is one pointer write, not a second walk.

Forgetting to attach the remainder drops the leftover chain on the floor. Empty inputs need no special case: the while never runs, tail.next becomes the other head (or null), you return dummy.next.

Note: On a tie, <= takes from a. Either choice stays sorted; pick one and stick to it so the walk is deterministic.

What interviewers usually poke next

  • Recursive version. Take the smaller head, set head.next to the merge of the rest, return that head. Mention the O(m + n) stack bill; iterative dummy is the default.
  • Merge k lists. Pairwise this merge, or a heap of current heads. Same splice, more sources.
  • Sort List. Merge sort on a linked list uses this as the combine step. Future poke: /interview/linked-lists/medium/sort-list/.
  • Reorder List. Split, reverse the back half, then merge the two halves. The splice here is the last move; that prompt is its own problem.
  • Do it by copying values. Correct numbers, wrong identity, extra space. Say why in-place is the bill they asked for.

You are done with this problem when you can merge 2 → 5 and 3 → 5 on a whiteboard without allocating new nodes, and you can name the empty-list return without a special case.