Flattening a Linked List

flatten_linkedList

/*
https://practice.geeksforgeeks.org/problems/flattening-a-linked-list/1#

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. */

void merge(Node *l1, Node *l2) {
    Node *curr = l1;
    l1 = l1->bottom;
    
    while(l1 && l2) {
        
        if(l1->data < l2->data) {
            curr->bottom = l1;
            l1 = l1->bottom;
        } else {
            curr->bottom = l2;
            l2 = l2->bottom;
        }
        
        curr = curr->bottom;
    }
    
    if(l1) curr->bottom = l1;
    if(l2) curr->bottom = l2;
}
    
Node *flatten(Node *node)
{
   Node *dummy = new Node(0);
   Node *prev = node;
   
   while(node) {
       merge(dummy, node);
       node = node->next;
       prev->next = nullptr;
   }
   
   dummy->next = nullptr;
   return dummy->bottom;
}