22. Flattening a Linked List

Given a Linked List of size N, where every node represents a sub-linked-list and contains two pointers: (i) a next pointer to the next node, (ii) a bottom pointer to a linked list where this node is head. Each of the sub-linked-list is in sorted order. Flatten the Link List such that all the nodes appear in a single level while maintaining the sorted order. Note: The flattened list will be printed using the bottom pointer instead of next pointer. For more clearity have a look at the printList() function in the driver code.

Example 1:

Input:
5 -> 10 -> 19 -> 28
|     |     |     | 
7     20    22   35
|           |     | 
8          50    40
|                 | 
30               45
Output:  5-> 7-> 8- > 10 -> 19-> 20->
22-> 28-> 30-> 35-> 40-> 45-> 50.
Explanation :
The resultant linked lists has every 
node in a single level.
(Note: | represents the bottom pointer.)

Example 2:

Input:
5 -> 10 -> 19 -> 28
|          |                
7          22   
|          |                 
8          50 
|                           
30              
Output:
 5->7->8->10->19->22->28->30->50
Explanation:
The resultant linked lists has every
node in a single level.

(Note: | represents the bottom pointer.)

Solution:

struct Node{
	int data;
	struct Node * next;
	struct Node * bottom;
	
	Node(int x){
	    data = x;
	    next = NULL;
	    bottom = NULL;
	}
	
};

/*  Function which returns the  root of 
    the flattened linked list. */
    
Node *merge(Node *r1, Node *r2){
  
  if(!r1){
      return r2;
  }
  
  if(!r2){
      return r1;
  }
  
  Node *sort;
  Node *head;
  
  if(r1->data <= r2->data){
      sort = r1;
      r1 = r1->bottom;
  }
  else {
      sort= r2;
      r2 = r2->bottom;
  }
  
  head = sort;
  
  while(r1 && r2){
      
      if(r1->data <= r2->data){
      sort->bottom = r1;
      r1 = r1->bottom;
     }
       else {
      sort->bottom = r2;
      r2 = r2->bottom;
    }
    
    sort = sort->bottom;
  }
  
  
  if(!r2){
      sort->bottom = r1;
  }
  else{
      sort->bottom = r2;
  }
  
  return head;
  
}   

Node *flatten(Node *root)
{
   // Your code here
   if(root == NULL || root->next == NULL){
       return root;
   }
   
   root->next = flatten(root->next);
   root = merge(root, root->next);
   
   return root;
}