flattens 2 D linked list to a single sorted link list

Write a function flatten() which flattens this linked list with each node down sorted link list to a single link list with all the elements in sorted order.

We have given Two methods in O(n^2) here.
for different linked list.

5 -> 7 ->  9 -> 18
 |    |    |    |
10    8    14   20
 |    |    |    |
11    8.5  19   22
 |    |         |
12    13        24
 |    
15

Method 1 :
Keep Two pointers and print all elements and ie: 5,10,11,12,15,7,6,8,13 … and sort the array.
Time Complexity : O(n log n)

Method 2 :
We can Think to implement a method via which all numbers takes appropriate place in sorted order.

With Above Example.

1) Store first main list's element in Auxiliary Array 
Temp[]:  5 - 7 - 9 - 18. This Temp is sorted.

2) Take first Down elements and With the divide and conquer logic 
 place them at appropriate position.
 say 10.

- 10 > 5 , 10 <18
- divide in sub array {5,7},{9,18} 
- 10 < 5, 10 > 7 10 won't come in this array part.
- 10 > 9, 10 < 18 put 10 in between 
- Result set 5,7,9,10,18
3) Similarly do for all elements in fist down list

 after first down link list
 Result Set : 5,7,9,10,11,12,15,18.
 take second list elements
 say 8.

- 8 > 5 , 8 < 18
- divide {5,7,9,10} and {11,12,15,18} 
- 8 > 5 , 8 < 10 & 8 < 11 ,8 < 18 => 8 won't come in this array part
- divide {5,7} {9,10} 
- repeating same we can put 8 in after 5, 7 and
- Result set will be 5,7,8,10,11,12,15,18.. like wise complete all.

Time complexity O(n log n) where n is total number of elements

Method 3 : Use Merge sort  – Take one first two list with 5 and 7 as head node.
– Merge and sort them in any one auxiliary list say “Result”
– and continue with Result and other lists.
– eg.Take below trace of calls to understand code

1)merge(5,7)

2)if 5 < 7 : result = 5;
  result->down = merge (10,7)
  //in next call it will return 7.
  // so result list will be 5-7.
 
3) if 10<7 : X
   result = 7
   result->down = merge (8,10);
 // hence result will be 5-7-8 in next call .
In next steps result will continue like this and produce sorted flatten Linked List

Code : 

Node* merge( Node* a, Node* b )
{
    // If first list is empty, the second list is result
    if (a == NULL)
        return b;
 
    // If second list is empty, the first list is result
    if (b == NULL)
        return a;
 
    // Compare the data members of head nodes of both lists
    // and put the smaller one in result
    Node* result;
    if( a->data < b->data )
    {
        result = a;
        result->down = merge( a->down, b );
    }
    else
    {
        result = b;
        result->down = merge( a, b->down );
    }
 
    return result;
}
 
// The main function that flattens a given linked list
Node* flatten (Node* root)
{
    // Base cases
    if ( root == NULL || root->right == NULL )
        return root;
 
    // Merge this list with the list on right side
    return merge( root, flatten(root->right) );
   
}

-IF YOU LIKE OUR EFFORT, PLEASE LIKE AND SHARE OUR FB-PAGE AND SITE