Flattening a Linked List

Implement flatten

Picture a collection of lists, each one already sorted, gathered together in some fixed order. Flatten every one of them into a single list that's still fully sorted, with every value from every original list included exactly once. This is the same shape as merging k sorted lists — it just arrives framed as separate sorted sub-lists that need combining rather than nodes with an extra pointer. Splitting the collection in half, recursively flattening each half down to one sorted list, and then merging those two results with a standard two-pointer splice keeps the total work proportional to N log k instead of degrading toward N times k if the lists were folded in one at a time.

Example 1:

Input: lists = [[5,10],[2,7],[1,9]]

Output: [1,2,5,7,9,10]

Example 2:

Input: lists = [[3,6,9]]

Output: [3,6,9]

Example 3:

Input: lists = [[],[]]

Output: []

+ 4 hidden test cases run on Submit.

Constraints:

  • 1 ≤ number of top-level lists (k) ≤ 50
  • 0 ≤ nodes per list ≤ 20
  • -1000 ≤ node value ≤ 1000
  • Each individual list is already sorted in increasing order

lists =

[[5,10], [2,7], [1,9]]