Partitioning a linked list around a given value and keeping the original order | Link list Node ; A utility function to create a new node ; Function to make two separate lists and return head after concatenating ; Let us initialize first and last nodes of three linked lists 1 ) Linked list of values smaller than x . 2 ) Linked list of values equal to x . 3 ) Linked list of values greater than x . ; Now iterate original list and connect nodes of appropriate linked lists . ; If current node is equal to x , append it to the list of x values ; If current node is less than X , append it to the list of smaller values ; Append to the list of greater values ; Fix end of greater linked list to NULL if this list has some nodes ; If smaller list is empty ; If smaller list is not empty and equal list is empty ; If both smaller and equal list are non - empty ; Function to prvar linked list ; Start with the empty list
class Node { constructor ( ) { this . data = 0 ; this . next = null ; } } function newNode ( data ) { var new_node = new Node ( ) ; new_node . data = data ; new_node . next = null ; return new_node ; } function partition ( head , x ) { var smallerHead = null , smallerLast = null ; var greaterLast = null , greaterHead = null ; var equalHead = null , equalLast = null ; while ( head != null ) { if ( head . data == x ) { if ( equalHead == null ) equalHead = equalLast = head ; else { equalLast . next = head ; equalLast = equalLast . next ; } } else if ( head . data < x ) { if ( smallerHead == null ) smallerLast = smallerHead = head ; else { smallerLast . next = head ; smallerLast = head ; } } else { if ( greaterHead == null ) greaterLast = greaterHead = head ; else { greaterLast . next = head ; greaterLast = head ; } } head = head . next ; } if ( greaterLast != null ) greaterLast . next = null ; if ( smallerHead == null ) { if ( equalHead == null ) return greaterHead ; equalLast . next = greaterHead ; return equalHead ; } if ( equalHead == null ) { smallerLast . next = greaterHead ; return smallerHead ; } smallerLast . next = equalHead ; equalLast . next = greaterHead ; return smallerHead ; } function printList ( head ) { var temp = head ; while ( temp != null ) { document . write ( temp . data + " " ) ; temp = temp . next ; } } var head = newNode ( 10 ) ; head . next = newNode ( 4 ) ; head . next . next = newNode ( 5 ) ; head . next . next . next = newNode ( 30 ) ; head . next . next . next . next = newNode ( 2 ) ; head . next . next . next . next . next = newNode ( 50 ) ; var x = 3 ; head = partition ( head , x ) ; printList ( head ) ;