### 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