262. Flatten a Linked List

You are given m separate sorted linked lists (each list's length followed by its sorted values), representing a top-level list whose nodes each have a 'child' pointer to one of these sorted sub-lists. Flatten all of them into a single fully sorted linked list by merging every value together, and print the result.

Input: The first line contains an integer m, the number of top-level nodes. Then for each of the m child lists: a line with that list's length, followed by a line of that many space-separated sorted integers (the values line is absent when a sub-list's length is 0). Output: Print the fully flattened, fully sorted sequence of every child list's values, space-separated, on one line.

1 <= m <= 100, 0 <= each sub-list's length <= 1000

The final result must contain EVERY value from every child list, fully sorted, REGARDLESS of the order in which you choose to merge the child lists together - the merging order affects efficiency, not correctness.

Given a top-level list whose nodes each have their own sorted 'child' sub-list, merge everything into one single sorted list. Brute force: Collect every value from every child list into one big array, sort the whole array, and rebuild a list from it - this works but costs O(N log N) where N is the total element count, ignoring that each child list is ALREADY sorted. Optimised: Since every child list is already individually sorted, repeatedly merging pairs (or using a min-heap across all lists at once) combines everything using only the standard two-sorted-list-merge technique repeatedly - no full re-sort of everything is ever needed.

Walk through the top-level list and every child sub-list, dumping all values into one big array, then sort that array and rebuild a single linked list from the sorted values. This is correct because sorting always produces the right final order regardless of how the values were originally distributed among the sub-lists, but it completely ignores the fact that each sub-list is already individually sorted, so it does far more comparison work than necessary. Time: O(N log N) Space: O(N)

Push the first node of every one of the m sub-lists into a min-heap keyed by value, then repeatedly pop the smallest node, append it to the output list, and push that node's own successor (from its original sub-list) into the heap if one exists, continuing until the heap is empty. This is correct because the heap always exposes the globally smallest remaining candidate across all m lists at once, so every value gets appended to the output in fully sorted order. It is faster than merging lists sequentially because each of the N total values only costs a single O(log m) heap operation instead of being re-compared against an ever-growing merged list. Time: O(N log m) Space: O(m)

Take the first two sorted sub-lists and merge them into one sorted list using the standard two-pointer merge-two-sorted-lists technique, then merge that result with the third sub-list, then with the fourth, and so on until all m sub-lists have been folded in. This is correct because merging two sorted lists always yields a sorted list, and repeating that against every remaining sub-list eventually incorporates all values in sorted order. It is an improvement over sorting from scratch because it exploits the existing order within each sub-list, though the growing merged list gets re-scanned against each new sub-list, so the total work still scales with the number of sub-lists. Time: O(N * m) Space: O(1)

1. Recognize this as the SAME idea as merging k sorted linked lists - either repeatedly merge PAIRS of sorted lists, or use a min-heap across all of them at once. 2. A common approach merges the child lists two at a time, working from the LAST pair forward, reusing the standard two-sorted-lists merge each time. 3. Continue merging until only one fully sorted list remains, containing every value from every child list.

Time: O(N log m), where N is the total number of nodes across all m child lists, if merging pairs in a balanced way (or using a min-heap approach) - O(N * m) if merging one child list at a time sequentially without balancing. Space: O(1) extra space if relinking existing nodes directly during merges (beyond recursion stack if implemented recursively).

a sub-list of length 0, contributing no values at all; m = 1 (only one child list to flatten); duplicate values across different child lists, since values aren't stated distinct.

Be ready to connect this directly to 'Merge K Sorted Linked Lists' - this problem is essentially the identical challenge, just framed as 'child pointers' instead of 'k separate given lists'.