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