CareerCup

Do they want a clever solution? The following one is just linear traversal, nothing fancy.

Node insert(Node n, Node head) {
	Node cur = head;		
	while (cur.next != head) {
		if (cur.value < n.value && cur.next.value >= n.value) {
			Node next = cur.next;
			cur.next = n;
			n.next = next;
return head;
		}
	}
	if (n.value > cur.value) {
		cur.next = n;
		n.next = head;
		return head;
	}
	if (n.value <= head.value) {
		cur.next = n;
		n.next = head;
		return n;
	}
}

It is pretty easy one I think. Suppose you have new node X to be inserted. Pick up any node in CLL, traverse until you find one, for example A, which A < X and A->next > X, then insert it after A. Just be careful the smallest node, which has a feature of FirstNode < PreviousNode. Complexity is O(n).

Better will be to keep track of mid point of CLL...whenever u insert a node....so that u can start traversing from start or the midpoint....can reduce half traversal....;)

public boolean(Node node){
	Node current=head;
	Node previous=null;
	if(node.value<=head.value){
		node.next=head;
		head=node;
		return true;
		}
	else{
		while(current.next.value>=current.value){
			previous=current;
			current=current.next;
			if(node.value>previous.value && node.value<current.value){
				previous.next=node;
				node.next=current;
				return true;
			}
	}
		return false;
}

@Anonymous: The above solution may fail if we are inserting a node at head (if condition in your program). You haven't included the logic for connecting last node to newly created head.

public static Node insertCLL(Node start, Node insertNode) {

  if(start == null || insertNode == null) {
    return;
  }

  Node current = start;

  while(current.getNext() != start) {
    if(current.getData() < insertNode.getData()
    && curent.getNext().getData() > insertNode.getData() ) {
 
      target.setNext(current.getNext());
      current.setNext(target);
      return;
    }
    current = current.getNext();
  }

  target.setNext(current.getNext());
  current.setNext(target);

  if(target.getData() < start.getData()) {
   start = target;
  }
}

Includes logic for inserting both at head and final:
1. if value > current and value < next insert (base case)
2. if value > current and current < next insert (tail)
3. if value < next and current > next insert (head)

public class CLLInsert {
	
	public static class CLLNode {
		public CLLNode next;
		public int value;
		
		public CLLNode(CLLNode next, int value) {
			super();
			this.next = next;
			this.value = value;
		}
	}
	
	public static void insert(CLLNode cll, int val) {
		insert(cll, new CLLNode(null, val));
	}

	public static void insert(CLLNode cll, CLLNode n) {
		boolean inserted = false;
		while (!inserted) {
			if (n.value < cll.next.value) {
				if (n.value >= cll.value
					|| cll.value > cll.next.value) {
					inserted = true;
				}
			} else if (cll.value > cll.next.value
					&& n.value >= cll.value) {
				inserted = true;
			}
			if (inserted) {
				n.next = cll.next;
				cll.next = n;
			}
			cll = cll.next;
		}
	}

}

What happens if the list contain million's of numbers. To make it efficient I propose the following algorithm.
1. Hash an array of 100 elements which always point to the various parts of the linked list
2. When inserting an element, search through the array to find the two range to search within the linked list, call it as low and high pointers.
3. Increment low and decrement high, till you find a suitable place to insert the new node.
4. Insert the new node.

Another method. O(n) complexity.
Algorithm
1. Find whether the element to be inserted is less than the refernceNode. If it is less, then find the inflexion point where the order is changing
2. then find the position where the element to be inserted from the next loop.
3. If element is greater than the reference node, then go to second loop where we are finding the node which is first bigger than the element and tempList is pointing to the previous node.
4. Last: Previous is the present node in the tempList. tempList is moving one more postion.
5. Then add the element at that position

class  CircularSortedList
    {
        public static Node head = null;
        public static Node Insert(Node list,int value, Node referenceNode)
                {
            if(referenceNode==null)
            return null;

            Node newNode = new Node(value);
            if(list==null)
              {
                newNode=newNode.Next;
                return newNode;
              }             
            Node tempList=referenceNode;
            Node endNode=referenceNode;
            Node previous= referenceNode;
            //here finding point where the newNode should be added
            //if value is less than the reference node
            if(endNode.Data>value)
            {
            while(tempList.Next!=endNode && tempList.Next.Data >= value)
                {                 
                //finding the inflexion point
                if (tempList.Data > tempList.Next.Data)
                {
                break;
                }
                tempList=tempList.Next;
               }
            }
            while (tempList.Next != endNode )
            {             
            //Starting from the lowest element now.
              
                if (tempList.Next.Data > value || tempList.Next.Data < tempList.Data && tempList.Data < value)
                {
                break;                
                }                
                tempList=tempList.Next;
            }
            previous = tempList;
            tempList = tempList.Next;            
            previous.Next=newNode;
            newNode.Next=tempList;          
        return newNode;
        }

public class CircularLinkedList {

	private DataNode head;

	public void initialize() {
		head = null;
	}

	public void addNode(DataNode newNode) {
		boolean isRootUpdated = false;
		if (head == null) {
			head = newNode;
			head.next = head;
			return;
		} else {
			DataNode temp = head, prevHead = head;
			while (temp.next.data <= newNode.data && temp.next != head) {
				temp = temp.next;
			}
			if (temp.data > newNode.data) {
				newNode.next = head;
				head = newNode;
				isRootUpdated = true;
			} else {
				newNode.next = temp.next;
				temp.next = newNode;
			}
			if (isRootUpdated) {
				DataNode curr_end = temp;
				while (curr_end.next != prevHead) {
					curr_end = curr_end.next;
				}
				curr_end.next = head;
			}
		}
	}

	void printList() {
		DataNode temp = head;
		if (temp == null) {
			System.out.println("List Empty");
			return;
		}
		System.out.print(head.data + " - > ");
		while (temp.next != head) {
			temp = temp.next;
			System.out.print(temp.data + " -> ");
		}
		System.out.println();
	}

	public static void main(String[] args) {
		CircularLinkedList linkedList = new CircularLinkedList();
		linkedList.initialize();
		DataNode newNode = new DataNode(1);
		linkedList.addNode(newNode);
		newNode = new DataNode(2);
		linkedList.addNode(newNode);
		linkedList.printList();
		newNode = new DataNode(5);
		linkedList.addNode(newNode);
		newNode = new DataNode(4);
		linkedList.addNode(newNode);
		linkedList.printList();
		newNode = new DataNode(8);
		linkedList.addNode(newNode);
		newNode = new DataNode(4);
		linkedList.addNode(newNode);
		newNode = new DataNode(15);
		linkedList.addNode(newNode);
		newNode = new DataNode(-1);
		linkedList.addNode(newNode);
		linkedList.printList();
	}
}

class DataNode {

	int data;
	DataNode next;

	DataNode(int nodeData) {
		data = nodeData;
		next = null;
	}
}

void insertNode(int data, Node head){
if(head == null){
head = new Node(data, null);
return;
}
if(head.getData() > data){
head = new Node(data, head);
return
}
Node tmp = head;
while(tmp.getData < data && tmp.getNext() != head){
tmp = tmp.getNext();
}
tmp.setNext(new Node(data, tmp.getNext());
}

class Node{
int data;
Node next;
public Node(data, next){
this.data = data;
this.next = next;
}
public void setData(int value){
data = value;
}
public int getData(){
return data;
}
public void setNext(Node value){
next = value;
}
public Node getNext(){
return next;
}

}

public class InsertCircular {
	
public static void main(String [] args){
	CircularLinkedList myList=null;
	myList=insert(myList, 0);
	myList.printList();
	myList.next=new CircularLinkedList(3);
	myList.next.next=new CircularLinkedList(4);
	myList.next.next.next=myList;
	//smyList=insert(myList, 2);
	myList.printList();
	
	
}

public static CircularLinkedList insert(CircularLinkedList node,int value){
if(node==null){
	return new CircularLinkedList(value);
}
else 
	if(node.next==node){
	node.next= new CircularLinkedList(value);
	node.next.next=node;
	return node.value<value ? node : node.next;
	}
	else
		if(value<node.value){
			CircularLinkedList current=node;
			while(current.next!=node ){
				current=current.next;
			}
			current =current.next;
			current.next = new CircularLinkedList(value);
			current.next.next=node;
			return current.next;
		}	
			CircularLinkedList current=node;
			while(current.next!=node && current.value<=value){
				current=current.next;
			}
			CircularLinkedList newCurrent=current;
			current = new CircularLinkedList(value);
			current.next.next=newCurrent;
			return current.next;
		

}
	

}

public class CircularLinkedList {
int value;
CircularLinkedList next;

public CircularLinkedList(int  value){
	value=this.value;
	next=this;
}

public void printList(){
	if(this==null)
		return;
	CircularLinkedList current=this;
	do{
		
		System.out.println(current.value+" ");
		current=current.next;
		
	}while(current!=this);
	System.out.println(" ");
}
}