Problem Statement:
You are given a LL that has below properties:
1. Pointer to the next node in the main list
2. Pointer to a sorted LL with the node is head
Example
Input: 4 -> 9 -> 18 -> 27 | | | | V V V V 6 18 21 32 | | | V V V 7 40 30 Output: 4 -> 6 -> 7 -> 9 -> 18 -> 18 -> 21 -> 27 -> 30 -> 32 ->40
Solution
In the solution we use Merge Sort.
We merge lists one by one.
Then we recursively merge the current list with already flattened list.
Solution in C++
#include <algorithm> //visit www.ProDeveloperTutorial.com for 450+ solved questions #include <iostream> #include <string> #include <unordered_map> #include <vector> #include <stack> using namespace std; typedef struct Node { int data; struct Node *right; struct Node *down; } Node; void push (Node** head_ref, int new_data) { Node* new_node = (Node *) malloc(sizeof(Node)); new_node->right = NULL; new_node->data = new_data; new_node->down = (*head_ref); (*head_ref) = new_node; } void printList(Node *node) { while (node != NULL) { printf("%d ", node->data); node = node->down; } } Node* merge( Node* a, Node* b ) { if (a == NULL) return b; if (b == NULL) return a; Node* result; if (a->data < b->data) { result = a; result->down = merge( a->down, b ); } else { result = b; result->down = merge( a, b->down ); } result->right = NULL; return result; } Node* flatten_list (Node* root) { if (root == NULL || root->right == NULL) return root; return merge( root, flatten_list(root->right) ); } int main() { Node* root = NULL; /* 4 -> 9 -> 15 -> 20 | | | | V V V V 5 16 20 25 | | | V V V 6 40 30 | | V V 7 35 */ push( &root, 7 ); push( &root, 6 ); push( &root, 5 ); push( &root, 4 ); push( &( root->right ), 16 ); push( &( root->right ), 9 ); push( &( root->right->right ), 40 ); push( &( root->right->right ), 20 ); push( &( root->right->right ), 15 ); push( &( root->right->right->right ), 35 ); push( &( root->right->right->right ), 30 ); push( &( root->right->right->right ), 25 ); push( &( root->right->right->right ), 20 ); root = flatten_list(root); printList(root); return 0; }
Output:
4 5 6 7 9 15 16 20 20 25 30 35 40