Merge k sorted linked lists using a custom comparator
A unified inbox shows notifications from several sources (mentions, reviews, deploys) in one timeline. Each source already delivers its items as a sorted singly linked list. Copying everything into an array and sorting it would ignore that work, so the inbox merges the lists directly.
Implement mergeSortedLists(lists, compare). It merges k sorted linked lists into one sorted linked list and returns its head.
mergeSortedLists(lists, compare?) // => head node, or null
// node: { value, next } (next is the following node, or null)
lists is an array of list heads. A head can be null (an empty list). Each list is sorted according to compare.compare(a, b) receives two node values and works like the comparator of Array.prototype.sort: negative means a comes first, positive means b comes first, and 0 means they are equal. It defaults to ascending numbers: (a, b) => a - b.compare. Return null when there are no nodes at all.lists comes first. Nodes from the same list keep their original order.next pointers. Do not create new nodes. The last node’s next must be null.N nodes in total, run in O(N log k) time. Comparing every list head on every step is O(N·k) and too slow for many sources.// Written as arrays for readability; the real input is linked nodes.
mergeSortedLists([[1, 4, 9], [2, 3, 10], [5]]);
// => 1 -> 2 -> 3 -> 4 -> 5 -> 9 -> 10
mergeSortedLists([null, null]);
// => null
const newestFirst = (a, b) => b.time - a.time;
mergeSortedLists([mentions, reviews, deploys], newestFirst);
// => every notification, newest first; equal times keep the order mentions, reviews, deploys