A billing pipeline is given k already-sorted invoice queues — overnight ACH, same-day cards, three regional log shards — each a singly linked list ordered by invoice id. Finance wants one merged stream, still sorted, without allocating a new pile of invoice objects. The intern version walked every list, dumped amounts into an ArrayList, sorted, and built a fresh chain. The numbers were right. The nodes were not. Downstream jobs that still held a node from a source queue were looking at the old successor.

Merging k sorted singly linked lists means rewiring next pointers so one sorted chain uses the same nodes. Merge Two Sorted Lists already taught dummy-head splice for two sources: always take the smaller current node. Here there are k sources, so a heap of current heads replaces the two-pointer comparison. This is an interview writeup, not a heap or linked list lecture. Those posts own sift and splice. Here we only care about poll the smallest head, splice it, offer that list’s next.

The problem

Given an array of k heads of sorted singly linked lists, merge them into one sorted list by rewiring the existing nodes. Return the new head. The array may be empty. Any head may be null.

lists:
  4 → 11
  1 → 6 → 14
  8 → 9
merged = 1 → 4 → 6 → 8 → 9 → 11 → 14

lists = []
merged = empty

lists = [empty, 8 → 9, empty]
merged = 8 → 9

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 extra space should stay near k, not near the total length.

Copy, sort, rebuild is the honest brute

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

ListNode mergeKByCopy(ListNode[] lists) {
    List<Integer> vals = new ArrayList<>();
    for (ListNode head : lists) {
        for (ListNode n = head; 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 shards this is a rounding error. In production you paid O(N log N) extra time, O(N) extra nodes, and you threw away the objects callers still held. Each list was already sorted. You did not need a second global sort. Pairwise two-list merge is the other honest path that does keep identity; it is the heap-free alternative below, not this dump.

Heap of current heads, splice onto a dummy tail

Seed a min-heap with each non-null head. PriorityQueue is a min-heap; the comparator reads ListNode.val, so poll returns the smallest current front. A dummy head gives the first splice a predecessor. Keep tail on the last node of the merged prefix.

  • Poll the smallest node, splice it onto tail, advance tail.
  • If that node has a next, offer it. That list’s new front re-enters the heap.
  • Repeat until the heap is empty.

You never dump values. You never allocate a replacement chain. Empty heads never enter the heap, so they cannot NPE the comparator.

Walk 4 → 11, 1 → 6 → 14, and 8 → 9:

seed: heap [1, 4, 8]     dummy → null,  tail=dummy

poll 1, splice, offer 6     dummy → 1           heap [4, 6, 8]
poll 4, splice, offer 11    dummy → 1 → 4       heap [6, 8, 11]
poll 6, splice, offer 14    dummy → 1 → 4 → 6   heap [8, 11, 14]
poll 8, splice, offer 9     dummy → … → 8       heap [9, 11, 14]
poll 9, splice, no next     dummy → … → 8 → 9   heap [11, 14]
poll 11, splice, no next    dummy → … → 11      heap [14]
poll 14, splice, no next    dummy → … → 14      heap []

return dummy.next

The Java is that walk:

ListNode mergeKLists(ListNode[] lists) {
    PriorityQueue<ListNode> heap = new PriorityQueue<>(
            (a, b) -> Integer.compare(a.val, b.val));
    for (ListNode head : lists) {
        if (head != null) {
            heap.offer(head);
        }
    }
    ListNode dummy = new ListNode(0);
    ListNode tail = dummy;
    while (!heap.isEmpty()) {
        ListNode smallest = heap.poll();
        tail.next = smallest;
        tail = tail.next;
        if (smallest.next != null) {
            heap.offer(smallest.next);
        }
    }
    return dummy.next;
}

Time is O(N log k) — N total nodes, each offered and polled once, each heap op O(log k). Space is O(k) besides the dummy: the heap holds at most k nodes, one front per live list. Do not re-lecture sift at the whiteboard unless they ask.

Note: Skip null heads when you seed the heap. Offering null blows up the comparator. After a poll, offer next only when it is non-null — that is how a list leaves the heap for good. On a value tie, Integer.compare is enough; either order stays sorted.

What interviewers usually poke next

  • k = 1. Seed one head, then poll-and-offer walks that list alone. The merge is the list itself. A short-circuit return lists[0] is fine; say you noticed.
  • Empty lists in the array. Skip null heads at seed time. All-null or lists.length == 0 leaves the heap empty and returns dummy.next — null — with no special case.
  • Pairwise merge, no heap. Reuse merge two: divide and conquer, merge two at a time, same dummy splice. Time is still O(N log k) when you pair, worse if you fold left-to-right onto a growing result. Same identity rule; no PriorityQueue.
  • Dump values and sort. Correct numbers, wrong objects, O(N) extra nodes. Say why in-place is the bill they asked for.
  • Heap size. At most k entries — one current head per list that still has nodes. Not N.
  • Sort List. One unsorted list: cut, then merge. This prompt is already k sorted lists: heap of heads, no cut.
  • Find K Pairs / Design Twitter later. Same “k fronts in a min-heap” shape on different payloads. Those are their own posts.

You are done with this problem when you can merge 4 → 11, 1 → 6 → 14, and 8 → 9 on a whiteboard without allocating new nodes, and you can name why a null head never enters the heap.