Insertion in a sorted circular linked list when a random pointer is given | Java implementation of the approach ; 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 point of insertion ; Return the new head ; Function to print 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 ; Print the contents of the created list
import java . util . * ; import java . lang . * ; import java . io . * ; class GFG { static class Node { Node next ; int data ; } ; static Node create ( ) { Node new_node = new Node ( ) ; new_node . next = null ; return new_node ; } static Node find_head ( Node random ) { if ( random == null ) return null ; Node head , var = random ; while ( ! ( var . data > var . next . data var . next == random ) ) { var = var . next ; } return var . next ; } static Node sortedInsert ( Node head_ref , Node new_node ) { Node 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 ; } static void printList ( Node start ) { Node temp ; if ( start != null ) { temp = start ; do { System . out . print ( temp . data + " ▁ " ) ; temp = temp . next ; } while ( temp != start ) ; } } public static void main ( String args [ ] ) { int arr [ ] = { 12 , 56 , 2 , 11 , 1 , 90 } ; int list_size , i ; Node start = null ; Node temp ; for ( i = 0 ; i < 6 ; i ++ ) { if ( start != null ) for ( int 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 ) ) ; } }