Linked List: Flatten a Linked List

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

 

 

 

Write a Comment

Leave a Comment

Your email address will not be published. Required fields are marked *