python Algorithm-Sorted insert for circular linked list
Write a C function to insert a new value in a sorted Circular Linked List (CLL). For example, if the input CLL is following:

After insertion of 7, the above CLL should be changed to following

Algorithm:
Allocate memory for the newly inserted node and put data in the newly allocated node. Let the pointer to the new node be new_node. After memory allocation, following are the three cases that need to be handled.
1) Linked List is empty:
a) since new_node is the only node in CLL, make a self loop.
new_node->next = new_node;
b) change the head pointer to point to new node.
*head_ref = new_node;
2) New node is to be inserted just before the head node:
(a) Find out the last node using a loop.
while(current->next != *head_ref)
current = current->next;
(b) Change the next of last node.
current->next = new_node;
(c) Change next of new node to point to head.
new_node->next = *head_ref;
(d) change the head pointer to point to new node.
*head_ref = new_node;
3) New node is to be inserted somewhere after the head:
(a) Locate the node after which new node is to be inserted.
while ( current->next!= *head_ref &&
current->next->data < new_node->data)
{ current = current->next; }
(b) Make next of new_node as next of the located pointer
new_node->next = current->next;
(c) Change the next of the located pointer
current->next = new_node;
[ad type=”banner”]
Python Programming:
Output:
1 2 11 12 56 90
Time Complexity: O(n) where n is the number of nodes in the given linked list.
Case 2 of the above algorithm/code can be optimized. Please see this comment from Pavan. To implement the suggested change we need to modify the case 2 to following.
[ad type=”banner”]


