Flatten a linked list (each node has a bottom sub-list)

Medium

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.

Your solution ✓ Solved

Ctrl/⌘ + Enter to run

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);
}