/* 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;
}