Two Dimensional Linked Lists
You work for a package delivery company, and they need you to write code that flattens and sorts connected lists of package ids.
The input is a connected linked list where every node contains two pointers of the following type:
- A
nextpointer to the next node in the main list. - A
bottompointer to a linked list where this node is a head.
You have to flatten the linked list to a single linked list sorted in ascending order.
Note: All vertical lists are sorted in ascending order.
For example, below is a linked list structure:
The original linked list is: 6 -> 11 -> 20 -> 29
After flattening it, the sorted linked list will look like:
6 -> 8 -> 9 -> 11 -> 20 -> 21 -> 23 -> 29 -> 31 -> 36 -> 41 -> 46 -> 51The node structure has three fields, as mentioned: a next pointer, a bottom pointer, and a data part. There are multiple test cases. For each test case, this function will be called individually.
In this problem, the method signature is:
flattenLinkedList(head of data structure)Input
The first line of input contains an integer N, representing the number of head nodes connected.
The second line of input contains N space-separated numbers (M1, M2 ... MN), representing the number of elements in respective linked lists.
The third line of input contains all the linked list elements, starting with the 1st head node and covering all the elements through its down pointer, then the 2nd head node and covering all its elements through the down pointer, and so on.
Output
Return a pointer to the flattened linked list.
Constraints
1 <= N <= 501 <= Mi <= 201 <= Element of linked list <= 1000
Example #1
Input
4
2 2 3 2
8 10 9 16 11 13 15 14 20Output
8 9 10 11 13 14 15 16 20Explanation
The output is the sorted result of all the nodes.
This problem asks you to flatten a linked structure with both <code>next</code> and <code>bottom</code> pointers into one sorted linked list. Since each vertical list is already sorted, the key idea is to merge these lists rather than sort all nodes from scratch. A recursive or iterative merge approach works well: flatten the lists to the right first, then merge the current vertical chain with the flattened result. This is a classic linked-list merging problem and is often solved with a divide-and-conquer style approach.
