Untitled

/* Node structure  used in the program

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 *flatten(Node *curr)
{
    if (curr == NULL) return NULL;
    
    Node *l1 = curr;
    Node *l2 = flatten(curr -> next);
    Node *res = new Node(0);
    Node *ptr = res;
    
    while (l1 != NULL || l2 != NULL) {
        int val1 = l1 != NULL ? l1 -> data : INT_MAX;
        int val2 = l2 != NULL ? l2 -> data : INT_MAX;
        
        if (val1 < val2) {
            ptr -> bottom = l1;
            l1 = l1 -> bottom;
        } else {
            ptr -> bottom = l2;
            l2 = l2 -> bottom;
        }
        
        ptr = ptr -> bottom;
        ptr -> next = NULL;
        ptr -> bottom = NULL;
    }
    
    return res -> bottom;
}