CareerCup

Well I won't say its too easy unless you are allowed to traverse once and get the head aka minimum element....Three cases will arrive in this case...
1. value is less than givenNode.data.
2. value is greater than givenNode.data.
3. value is equal to given givenNode.data.

Implementation won't be much complex...but yes it will take time...if you consider all the cases like largest element and only 1 node in the list etc..

Java implementation...
docs.google.com/open?id=0Bw6L8Yy5eLJ3WGhpRENTcHNlekk

void insert(int n, node* random)
{
    if(random==NULL)
    {
	node* newNode = getNode(n);
	head = newNode;
	return;
    }
    if(random==random->next)
    {
        node* newNode = getNode(n);
        random->next = newNode;
        if(newNode->data<random->data)
		head = newNode;
        return;
    }
    node* current = random;
    node* nextNode = random->next;
    node* newNode = NULL;
    while()
    {
        if((n>=current->data && n<nextNode->data) ||
	   (n<current->data && n>nextNode->data))
	{
	    newNode = getNode(n);
	    newNode->next=nextNode;
	    current->next=newNode;
	    break;
	}
	current=nextNode;
	nextNode=nextNode->next;
    }
    if(n<current->data && n<nextNode->data)
        head = newNode;
    return;
}

public static Node Insert(Node node, int value)
        {
            Node current = null;
            Node tmp = null;
            Node newNode = null;

            // Empty list
            if (node == null)
            {
                if ((newNode = new Node()) == null)
                    throw new OutOfMemoryException();

                newNode.data = value;
                return (newNode);
            }

            if (node.data == value)
                return (InsertPrior(node, value));

            // Single node list
            if (node.next == null)
            {
                // Assert : node.prev == null
                return (InsertPrior(node, value));
            }

            for (current = node.next ; current != tmp ; current = current.next)
            {
                if (((current.prev.data < value) && (value <= current.data)) ||
                    ((current.prev.data > value) && (value >= current.data)))
                {
                    return (InsertPrior(current, value));
                }

                if (tmp == null)
                {
                    tmp = current;
                }
            }
            
            return (newNode);
        }

        public static Node InsertPrior(Node node, int value)
        {
            Node newNode;

            if ((newNode = new Node()) == null)
                throw new OutOfMemoryException();

            newNode.data = value;
            newNode.next = node;
            newNode.prev = node.prev;

            node.prev = newNode;
            newNode.prev.next = newNode;

            return (newNode);
        }

If two times list visit allowed the find minimum element in first visit...
then insertion is very easy ...

void Insert(list **head , int value)
{
list * itr = NULL;
list * pre = NULL;
if(*head == NULL)
{
*head = Node(value); //make new node
(*head)->next = *head;
return;
}
else
{
itr = *head;
pre = itr;
if(itr->value >= value)
{
while((itr != *root)&&(itr->value >= value))
{
pre = itr;
itr = itr->next;
}
}

while((itr != *root)&&(itr->value < value))
{
pre = itr;
itr = itr->next;
}
pre->next = Node(value);
pre->next->next = itr;
return;
}

}

Simple version:
public static void Insert(Node n,int value)
{
   if(n==null) return;  //Error condition.
   Node nw = new Node(value);
   if(n.next==null){  n.next=nw; return; }
   Node prev=n,next=n.next;
   while((prev.data>value&&next.data<value)||(prev.data<value&&next.data>value))
   {   prev=next;
       next=next.next;
   }
   prev.next=nw;
   nw.next=next;
}

class Node:
def __init__(self, v):
self.next = None
self.val = v
def __repr__(self):
return 'val = %d' % (self.val)

def insert(val, rNode):
if rNode == None:
rNode = Node(val)
rNode.next = rNode
return rNode
cur, next = rNode, rNode.next
while cur and next:
if cur.val < next.val:
if val >= cur.val and val <= next.val:
break
elif cur.val > next.val:
if val >= cur.val or val <= next.val:
break
elif cur.val == next.val:
if cur is next or cur.val == val:
break
cur = next
next = next.next

t = Node(val)
cur.next = t
t.next = next
return cur

///
public class LinkedListOperations
{

public void insertNodeInSortedCircularLinkedList(int data, Node refNode)
{
if(refNode == null)
System.out.println("Ref Node is null");

Node smallestNode = findTheSmallestNodeInCircularLinkedList(refNode);
Node largestNode = findTheLargestNodeInCircularLinkedList(refNode);

if(data >= largestNode.getData() || data <= smallestNode.getData())
{
Node node = new Node(data, largestNode.getNext());
largestNode.setNext(node);
return;
}

while(smallestNode.getNext().getData() < data)
smallestNode = smallestNode.getNext();

Node node = new Node(data, smallestNode.getNext());
smallestNode.setNext(node);
}


public Node findTheLargestNodeInCircularLinkedList(Node refNode)
{
Node largestNode = refNode;
if(refNode != null)
{
while(!largestNode.getNext().equals(refNode) && largestNode.getData() <= largestNode.getNext().getData())
largestNode = largestNode.getNext();

return largestNode;
}

return refNode;
}

public Node findTheSmallestNodeInCircularLinkedList(Node refNode)
{
Node smallestNode = refNode;

if(refNode != null){
while(!smallestNode.getNext().equals(refNode) && smallestNode.getData() >= smallestNode.getNext().getData())
smallestNode = smallestNode.getNext();
return smallestNode;
}

return refNode;

}

public void printCircularLinkedList(Node refNode)
{
if(refNode != null)
{
Node starter = refNode.getNext();
System.out.print(refNode.getData());

while(!starter.equals(refNode))
{
System.out.print(" ");
System.out.print(starter.getData());
starter = starter.getNext();
}
System.out.println();
}

}
\\\

we can take use of the property -- sorted linked list. we can build a skip list to shrink insert op speed (expectation O(lg(n))).

public static void insert(circle cir, circle random){
    while(true){
        if((random.value <= cir.value && random.next.value >= cir.value)|| (random.value >= random.next.value)){
            circle tmp = random.next;
            random.next = cir;
            cir.next = tmp;
            break;
        }else{
            random = random.next;
        }
    }
}
}

Sorry got deleted while editing it.. will repost it again ...

Node* insert(Node* random, int val )
{
Node* newNode = new Node;
newNode->data = val;
newNode->next = newNode;
//If node is empty
if( random == NULL )
return newNode;
Node* prev = random;
Node* start = random;
//For the cases where val > given node data
if( val > random->data )
{
while( (val > random->data) &&(prev->data <= random->data) && (random != start) )
{
prev = random;
random = random->next;
}
prev->next = newNode;
newNode->next = random;

}
//For the cases where val < given node data
else if( val < random->data)
{
while( (prev->data <= random->data) && ( random != start)
{
prev = random;
random = random->next;
}
while( (val > random->data) && (random != start))
{
prev = random;
random = random->next;
}
prev->next = newNode;
newNode->next = random;
}
//For the cases where val == given node data
else
{
newNode->next = random->next;
random->next = newNode;
}
return random;
}

Complexity is O(n)

Walk the list starting from the given node till the values start decreasing after an increase (or) increasing after decreasing. Now, we know the starting node. Walk the list checking where to insert the given value. O(N)

chekc where the value can be inserted

func(node* head,value){
curr = head;
while(curr!=head){ 
if(value > current->data && value <=curr->next->data)
 break;
}
node* temp = new node(value);
temp->next = curr->next;
curr->next = temp;
}

This comment has been deleted.