Flattening a linked list | Set 2 | C ++ program for Flattening a linked list using Heaps ; Structure of given Linked list ; Function to print the linked list ; Function that compares the value pointed by node and returns true if first data is greater ; Function which returns the root of the flattened linked list ; Min Heap which will return smallest element currently present in heap ; Push the head nodes of each downward linked list ; This loop will execute till the map becomes empty ; Pop out the node that contains element currently in heap ; Push the next node pointed by the current node into heap if it is not null ; Create new linked list that is to be returned ; Pointer to head node in the linked list ; Create and push new nodes ; Driver Code ; Given Linked List ; Flatten the list ; Print the flattened linked list
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int data ; struct Node * right ; struct Node * down ; Node ( int x ) { data = x ; right = NULL ; down = NULL ; } } ; void printList ( Node * Node ) { while ( Node != NULL ) { printf ( " % d ▁ " , Node -> data ) ; Node = Node -> down ; } } struct compare { bool operator() ( Node * a , Node * b ) { return a -> data > b -> data ; } } ; Node * flatten ( Node * root ) { Node * ptr = root ; Node * head = NULL ; priority_queue < Node * , vector < Node * > , compare > pq ; while ( ptr != NULL ) { pq . push ( ptr ) ; ptr = ptr -> right ; } while ( ! pq . empty ( ) ) { Node * temp = pq . top ( ) ; pq . pop ( ) ; if ( temp -> down != NULL ) { pq . push ( temp -> down ) ; } if ( head == NULL ) { head = temp ; ptr = temp ; ptr -> right = NULL ; } else { ptr -> down = temp ; ptr = temp ; ptr -> right = NULL ; } } return head ; } void push ( Node * * head_ref , int new_data ) { Node * new_node = ( Node * ) malloc ( sizeof ( Node ) ) ; new_node -> right = NULL ; new_node -> data = new_data ; new_node -> down = ( * head_ref ) ; ( * head_ref ) = new_node ; } int main ( ) { Node * root = NULL ; push ( & root , 30 ) ; push ( & root , 8 ) ; push ( & root , 7 ) ; push ( & root , 5 ) ; push ( & ( root -> right ) , 20 ) ; push ( & ( root -> right ) , 10 ) ; push ( & ( root -> right -> right ) , 50 ) ; push ( & ( root -> right -> right ) , 22 ) ; push ( & ( root -> right -> right ) , 19 ) ; push ( & ( root -> right -> right -> right ) , 45 ) ; push ( & ( root -> right -> right -> right ) , 40 ) ; push ( & ( root -> right -> right -> right ) , 35 ) ; push ( & ( root -> right -> right -> right ) , 20 ) ; root = flatten ( root ) ; printList ( root ) ; return 0 ; }