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.
这道题要求将一个带有 <code>next</code> 和 <code>bottom</code> 两种指针的二维链表扁平化，并最终输出为一个按升序排列的单链表。每一条纵向链表本身已经有序，因此核心思路不是重新排序所有节点，而是像归并多个有序链表一样，把各条链表逐步合并起来。实现时可以递归或迭代地先处理右侧主链，再把当前头节点的纵向链表与结果合并，最终得到完整的排序链表。由于题目输入规模不大，使用稳定的归并思路通常最自然，也最符合面试中的标准解法。
