You are given the head of a linked list where every node has two pointers: next (to the next node in the top-level list) and bottom (to a vertical sub-list). Every bottom sub-list is sorted, and the top-level list is sorted by next as well.
Flatten the structure into a single sorted list linked entirely through the bottom pointer, and return its head.
Input encoding: each line is one vertical sub-list — its first value is the top-level node, the rest hang off it via bottom; consecutive lines are joined via next. The judge reads your result by following bottom from the returned head.
- The number of nodes is in the range [0, 10^4] - Each vertical sub-list is sorted in non-decreasing order - 1 <= Node.val <= 10^5
Traverse the whole 2-D structure, dumping every value into an array. Sort the array, then string the values into a fresh bottom-linked list. Simple and correct, but ignores that the pieces are already sorted.
O(N log N) time, O(N) space.
Because every vertical list is already sorted, repeatedly merge the current flattened list with the next column (like merging two sorted lists, but along bottom). Fold left-to-right across the top-level list. No sorting, no extra array — just pointer rewiring.
O(N·k) time, O(1) space.
