Flattening a Linked List | head of list ; Linked list Node ; An utility function to merge two sorted linked lists ; if first linked list is empty then second is the answer ; if second linked list is empty then first is the result ; compare the data members of the two linked lists and put the larger one in the result ; Base Cases ; recur for list on right ; now merge ; return the root it will be in turn merged with its left ; * Utility function to insert a node at beginning of the linked list ; * 1 & 2 : Allocate the Node & Put in the data ; 3. Make next of new Node as head ; 4. Move the head to povar to new Node ; 5. return to link it back ; * Let us create the following linked list 5 -> 10 -> 19 -> 28 | | | | V V V V 7 * 20 22 35 | | | V V V 8 50 40 | | V V 30 45 ; flatten the list
var head ; class Node { constructor ( val ) { this . data = val ; this . down = null ; this . next = null ; } } function merge ( a , b ) { if ( a == null ) return b ; if ( b == null ) return a ; var result ; if ( a . data < b . data ) { result = a ; result . down = merge ( a . down , b ) ; } else { result = b ; result . down = merge ( a , b . down ) ; } result . right = null ; return result ; } function flatten ( root ) { if ( root == null root . right == null ) return root ; root . right = flatten ( root . right ) ; root = merge ( root , root . right ) ; return root ; } function push ( head_ref , data ) { var new_node = new Node ( data ) ; new_node . down = head_ref ; head_ref = new_node ; return head_ref ; } function printList ( ) { var temp = head ; while ( temp != null ) { document . write ( temp . data + " " ) ; temp = temp . down ; } document . write ( ) ; } 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 ( ) ;