DiffPush Tier Linked List · Hard Promblems of LL O(N), N = total nodes across all levels · O(1) beyond the merge recursion stack
A mail hub has a row of vertical chutes: each chute hangs a chain of already-sorted parcels off a top-level rail node, and every hanging chain is itself sorted. The outfeed, though, is a single belt — so the hub must collapse all the vertical chains into one continuous sorted run, read through the vertical (bottom) links only, leaving no horizontal rail behind. Merging two sorted chutes is cheap, so the plan is to swallow the rail right-to-left, each step merging the next chute's chain into the growing output.
Input: An array levels of sorted sub-lists — levels[i] is the vertical chain hanging beneath the i-th top-level node.
Output: The flattened chain's values in non-decreasing order (the single sorted run through the bottom pointers).
1 <= total nodes <= 10^5-10^9 <= value <= 10^9each sub-list and each chain is individually sortedInput: {"levels":[[5,7,8,30],[10,20],[19,22,50],[28,35,40,45]]}
Output: [5,7,8,10,19,20,22,28,30,35,40,45,50]
Four sorted chutes of different depths merge into one continuous run of 13 parcels; the horizontal rail dissolves entirely.
Input: {"levels":[[3],[1,2],[4,6]]}
Output: [1,2,3,4,6]
A one-parcel chute can overtake both neighbours once merged — chute depth carries no ordering meaning.