Linked Lists Combine K Sorted

You are given k singly-linked lists. Each list is already sorted ascending by value. Stitch them into ONE sorted singly-linked list and return its head. The work must be done in O(n log k) time, where n is the total node count and k is the number of input lists — beating both the O(n log n) "throw it in an array and sort" approach and the O(n × k) "merge them one at a time" approach.

This is the canonical follow-up to the heap question (a min-heap of list heads is the engine that gives us O(log k) per emission) and the linked-list question (every node still has the shape { value, next }). If you haven't done both, do them first — this question composes them. In practice, k-way merging of sorted streams is the engine inside external sorts (sorting data too large to fit in memory), inside database query planners that combine sorted indexes, and inside map-reduce shufflers — so this pattern is worth getting in your fingers.

Signature

type Node = { value: number; next: Node | null };

// `lists` is an array of head nodes. An entry may be null (an empty list).
// `lists` itself may be empty (k = 0).
function combineKSorted(lists: Array<Node | null>): Node | null;

Examples

// Three sorted lists, merged.
combineKSorted([
  { value: 1, next: { value: 4, next: { value: 5, next: null } } },
  { value: 1, next: { value: 3, next: { value: 4, next: null } } },
  { value: 2, next: { value: 6, next: null } },
]);
// → 1 → 1 → 2 → 3 → 4 → 4 → 5 → 6 → null

// An empty list mixed in is just skipped.
combineKSorted([
  { value: 1, next: { value: 2, next: null } },
  null,
  { value: 3, next: { value: 4, next: null } },
]);
// → 1 → 2 → 3 → 4 → null

// Single list passes straight through (by value).
combineKSorted([{ value: 7, next: { value: 9, next: null } }]);
// → 7 → 9 → null

// No lists at all → null.
combineKSorted([]);
// → null

Notes

• Time bound — your implementation must be O(n log k). A reference implementation that flattens-then-sorts is O(n log n); tests don't enforce timing, but the solution does (the heap-of-heads pattern).
• Node shape — plain objects: { value: number, next: Node | null }. No LinkedList class wrapper; the function operates on raw heads.
• No comparator parameter — assume < ordering on numeric value. Generalising to a custom comparator is covered in Going further.
• Do not mutate the input — callers still hold references to their original lists. The returned chain must be a fresh sequence of nodes; the input nodes' next pointers must be unchanged after the call.
• Empty inputs — lists.length === 0 returns null. So does an array of all-null entries.
• Negative numbers, duplicates, floats — all valid. Sort uses < so the usual numeric ordering applies; equal values may come out in any order between lists (stability is not required).