Flattening a linked list | Set 2 | Java program for Flattening a linked list using Heaps ; Linked list Node ; Function to print the linked list ; Class that compares the value pointed by node and make LinkedList sorted ; 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 pq 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 ; Flatten the list ; Print the flattened linked list
import java . util . * ; class Node { int data ; Node right , down ; Node ( int data ) { this . data = data ; right = null ; down = null ; } } class pair { int val ; Node head ; pair ( Node head , int val ) { this . val = val ; this . head = head ; } } public static void printList ( Node h ) { while ( h != null ) { System . out . print ( h . data + " ▁ " ) ; h = h . down ; } } class pairComp implements Comparator < pair > { public int compare ( pair p1 , pair p2 ) { return p1 . val - p2 . val ; } } class GFG { public static Node flatten ( Node root ) { Node ptr = root ; Node h = null ; PriorityQueue < pair > pq = new PriorityQueue < pair > ( new pairComp ( ) ) ; while ( ptr != null ) { pq . add ( new pair ( ptr , ptr . data ) ) ; ptr = ptr . right ; } while ( ! pq . isEmpty ( ) ) { Node temp = pq . poll ( ) . head ; if ( temp . down != null ) { pq . add ( new pair ( temp . down , temp . down . data ) ) ; } if ( h == null ) { h = temp ; ptr = temp ; ptr . right = null ; } else { ptr . down = temp ; ptr = temp ; ptr . right = null ; } } return h ; } public static Node push ( Node head_ref , int data ) { Node new_node = new Node ( data ) ; new_node . down = head_ref ; head_ref = new_node ; return head_ref ; } public static void main ( String args [ ] ) { Node head = null ; head = push ( head , 30 ) ; head = push ( head , 8 ) ; head = push ( head , 7 ) ; head = push ( head , 5 ) ; head . right = push ( head . right , 20 ) ; head . right = push ( head . right , 10 ) ; head . right . right = push ( head . right . right , 50 ) ; head . right . right = push ( head . right . right , 22 ) ; head . right . right = push ( head . right . right , 19 ) ; head . right . right . right = push ( head . right . right . right , 45 ) ; head . right . right . right = push ( head . right . right . right , 40 ) ; head . right . right . right = push ( head . right . right . right , 35 ) ; head . right . right . right = push ( head . right . right . right , 20 ) ; head = flatten ( head ) ; printList ( head ) ; } }