Merge Many Sorted Chains

Hard

You get an array chains holding the first nodes of several singly linked lists. The values in each list are in non-decreasing order; an empty list is given as None. The array itself may be empty. Join the nodes of all the lists into one list in non-decreasing order and return its first node (or None if there are no nodes at all). There can be many lists, so merging them one after another may turn out too slow.

Example 1

chains=[list_node([3, 7, 9]), list_node([-2, 7]), list_node([0, 4, 11, 12])] → [-2, 0, 3, 4, 7, 7, 9, 11, 12]

All the nodes of the three lists line up in non-decreasing order: -2, 0, 3, 4, 7, 7, 9, 11, 12.

Example 2

chains=[list_node([]), list_node([5]), list_node([])] → [5]

Two of the lists are empty, so the result is the single node 5.

Example 3

chains=[] → None

Constraints

0 ≤ len(chains) ≤ 10⁴
Each list has between 0 and 500 nodes
At most 10⁵ nodes in total
-10⁴ ≤ Node.val ≤ 10⁴
Each list is sorted in non-decreasing order

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Linked List Divide and Conquer Heap (Priority Queue)Merge Sort

Similar problems

Sorting a Linked List Medium Hand-Rolled Sort Medium City Block Outline Hard Smaller Values to the Right Hard Window Sums Within a Band Hard

Input

chains=[list_node([3, 7, 9]), list_node([-2, 7]), list_node([0, 4, 11, 12])]

Expected

[-2, 0, 3, 4, 7, 7, 9, 11, 12]

Run checks the first 3 tests in your browser. Submit checks all 6 tests on the server, hidden ones included.