Insertion in a sorted circular linked list when a random pointer is given | Node structure ; Function to create a node ; Function to find and return the head ; If the list is empty ; Finding the last node of the linked list the last node must have the highest value if no such element is present then all the nodes of the linked list must be same ; Return the head ; Function to insert a new_node in the list in sorted fashion . Note that this function expects a pointer to head node as this can modify the head of the input linked list ; If the list is empty ; If the node to be inserted is the smallest then it has to be the new head ; Find the last node of the list as it will be pointing to the head ; Locate the node before the povar of insertion ; Return the new head ; Function to prvar the nodes of the linked list ; Driver code ; Start with an empty linked list ; Create linked list from the given array ; Move to a random node if it exists ; Prvar the contents of the created list
class Node { constructor ( val ) { this . data = val ; this . next = null ; } } function create ( ) { var new_node = new Node ( ) ; new_node . next = null ; return new_node ; } function find_head ( random ) { if ( random == null ) return null ; var head , vari = random ; while ( ! ( vari . data > vari . next . data vari . next == random ) ) { vari = vari . next ; } return vari . next ; } function sortedInsert ( head_ref , new_node ) { var current = head_ref ; if ( current == null ) { new_node . next = new_node ; head_ref = new_node ; } else if ( current . data >= new_node . data ) { while ( current . next != head_ref ) current = current . next ; current . next = new_node ; new_node . next = head_ref ; head_ref = new_node ; } else { while ( current . next != head_ref && current . next . data < new_node . data ) { current = current . next ; } new_node . next = current . next ; current . next = new_node ; } return head_ref ; } function printList ( start ) { var temp ; if ( start != null ) { temp = start ; do { document . write ( temp . data + " " ) ; temp = temp . next ; } while ( temp != start ) ; } } var arr = [ 12 , 56 , 2 , 11 , 1 , 90 ] ; var list_size , i ; var start = null ; var temp ; for ( i = 0 ; i < 6 ; i ++ ) { if ( start != null ) for ( j = 0 ; j < ( Math . random ( ) * 10 ) ; j ++ ) start = start . next ; temp = create ( ) ; temp . data = arr [ i ] ; start = sortedInsert ( find_head ( start ) , temp ) ; } printList ( find_head ( start ) ) ;