Flatten a linked list (each node has a bottom sub-list)
Problem
Each node of a main list has a next pointer (to the next head) and a bottom pointer (to a sorted sub-list). The heads are also in sorted order. Flatten everything into a single sorted list linked through bottom.
Example 1
Input: 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
Also asked as: Flatten a Linked List
Test cases
No automated tests for this problem yet. Use the examples above to check your output.
This problem has no automated tests. Run executes your code and shows what it logs.
View solutionHide solution1 approach
1. Merge sub-lists from right to left
Time O(n·m) mergesSpace O(n) recursion
Recursively flatten the rest, then merge the current node’s sorted bottom-list with it.
function flatten(head) { if (!head || !head.next) return head; const merge = (a, b) => { const d = { bottom: null }; let t = d; while (a && b) { if (a.val <= b.val) { t.bottom = a; a = a.bottom; } else { t.bottom = b; b = b.bottom; } t = t.bottom; } t.bottom = a || b; return d.bottom; }; head.next = flatten(head.next); return merge(head, head.next);}