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

Write a function flatten() which flattens this link 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





































Labels:
,
,
,
,
,
,