Insertion in a sorted circular linked list when a random pointer is given | Python3 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
from random import randint NEW_LINE class Node : NEW_LINE INDENT def __init__ ( self ) : NEW_LINE INDENT self . next = None NEW_LINE self . data = 0 NEW_LINE DEDENT DEDENT def create ( ) : NEW_LINE INDENT new_node = Node ( ) NEW_LINE new_node . next = None NEW_LINE return new_node NEW_LINE DEDENT def find_head ( random ) : NEW_LINE INDENT if ( random == None ) : NEW_LINE INDENT return None NEW_LINE DEDENT head = None NEW_LINE var = random NEW_LINE while ( not ( var . data > var . next . data or var . next == random ) ) : NEW_LINE INDENT var = var . next NEW_LINE DEDENT return var . next NEW_LINE DEDENT def sortedInsert ( head_ref , new_node ) : NEW_LINE INDENT current = head_ref NEW_LINE if ( current == None ) : NEW_LINE INDENT new_node . next = new_node NEW_LINE head_ref = new_node NEW_LINE DEDENT elif ( current . data >= new_node . data ) : NEW_LINE INDENT while ( current . next != head_ref ) : NEW_LINE INDENT current = current . next NEW_LINE DEDENT current . next = new_node NEW_LINE new_node . next = head_ref NEW_LINE head_ref = new_node NEW_LINE DEDENT else : NEW_LINE INDENT while ( current . next != head_ref and current . next . data < new_node . data ) : NEW_LINE INDENT current = current . next NEW_LINE DEDENT new_node . next = current . next NEW_LINE current . next = new_node NEW_LINE DEDENT return head_ref NEW_LINE DEDENT def printList ( start ) : NEW_LINE INDENT temp = 0 NEW_LINE if ( start != None ) : NEW_LINE INDENT temp = start NEW_LINE while True : NEW_LINE INDENT print ( temp . data , end = ' ▁ ' ) NEW_LINE temp = temp . next NEW_LINE if ( temp == start ) : NEW_LINE INDENT break NEW_LINE DEDENT DEDENT DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 12 , 56 , 2 , 11 , 1 , 90 ] NEW_LINE start = None ; NEW_LINE temp = 0 NEW_LINE for i in range ( 6 ) : NEW_LINE INDENT if ( start != None ) : NEW_LINE INDENT for j in range ( randint ( 0 , 10 ) ) : NEW_LINE INDENT start = start . next NEW_LINE DEDENT DEDENT temp = create ( ) NEW_LINE temp . data = arr [ i ] NEW_LINE start = sortedInsert ( find_head ( start ) , temp ) NEW_LINE DEDENT printList ( find_head ( start ) ) NEW_LINE DEDENT