Flattening a Linked List
You are given a pointer p to node, having a key field, and two pointers to similar nodes. The
node p is the first node in the “main” list. The two pointers associated with each node are,
a. Next pointer to the next node in the linked list.
b. Down pointer which points to another linked list.
The node p starts up a “main” list, in which each node is connected to the next one through
the next pointers. Each node in this main list also starts up through its “down” pointers, a
“down” list of nodes, each connected to the next through down pointers. For the nodes in the
down list (other than the first node) the next pointers are necessarily nil. Each node belongs
to only one down list.
All linked lists are sorted. See the following example.
5 10 19 28
7 20 22 35
8 50 40 30 45Write a function flatten() to flatten the lists into a singly linked list. The flattened linked list
should also be sorted. Example: for the above input list, output list should be,
5 ->7 ->8->10->19->20->22->28->30->35->40->45->50