Problem. You're given k linked lists, each sorted ascending. Merge them into one sorted list and return its head. Let N be the total number of nodes.
[1 → 4 → 5, 1 → 3 → 4, 2 → 6] → 1 → 1 → 2 → 3 → 4 → 4 → 5 → 6
[] → None
Lesson 7.5 merged two lists in O(m + n), and its Change A sketched k lists with a heap. Here the k-way merge is the main event: four approaches, three different costs, and the reasons a heap is the default for streams while pairwise merging wins in other settings.
ML context. k-way merges are everywhere data is sharded: per-worker logs sorted by timestamp, per-shard search results sorted by score, sorted runs written to disk by a large sort, per-partition outputs of a map-reduce job. The heap merge reads each input sequentially and holds only k items in memory, which is exactly what you need when the inputs are files or network streams (Changes A and C).