Description: You are given a linked list where every node represents a linked list and contains two pointers of type:
(a) Pointer to next node in the main list (or the ‘right’ pointer)
(b) Pointer to a linked list where this node is head (or ‘down’ pointer).
All linked lists are sorted.
Write a function flatten() to flatten the lists into a single linked list.
If video does not load, Click here
We study two recursive functions flatten(root) and merge( a,b )to solve the problem
• If root== Null or root->right is null, return
• Else Merge this list with the list on right side by calling merge(root , flatten(root->right)) and return the merged pointer.
Merge( a,b )
• Uses the merge procedure to merge two linked lists pointed by a and b and returns a pointer to sorted linked list.