CareerCup

The idea is to just find the right position to insert by keeping two pointers and then either insert or swap values as needed

public class SortedCircularList
{
  //sentinel node.
  private final Node head;
  
  public SortedCircularList()
  {
  	head = new Node(null);
  	head.next = head;
  }
  
  public static void main(String ...args)
  {
     SortedCircularList list = new SortedCircularList();
     list.add(new Node(4));
     list.add(new Node(10));
     list.add(new Node(14));
     list.print();

     
     //Adding a node in between.
     list.add(new Node(0));
     list.print();
     list.add(new Node(11));
     list.print();     
  }
  
  
  public void add(Node n)
  {
     if(head.next==head)
     {
     	head.next = n;
     	n.next = head;
     	return;
     }
     
     //find the right pos.
     Node prev = head.next;
     Node cur = head.next.next;
     while(cur!=head && cur.data<=n.data)
     {
     	prev = cur;
		cur = cur.next;
     }
     
     n.next = prev.next;
     prev.next = n;
     if(n.data<prev.data)
     {
        int temp = n.data;
        n.data = prev.data;
        prev.data = temp;
     }     
  }
  
  
  
  
  
  public void print()
  {
     Node n = head.next;
     while(n!=head)
     {
     	System.out.println(n.data);
     	n = n.next;
     }
     System.out.println("******");
  
  }


  static final class Node
  {
  	private Node next;
  	private Integer data;
  	Node(Integer data)
  	{
  		this.data = data;
  	}
  }
}

public class SortedCircularList
{
  //sentinel node.
  private final Node head;
  
  public SortedCircularList()
  {
  	head = new Node(null);
  	head.next = head;
  }
  
  public static void main(String ...args)
  {
     SortedCircularList list = new SortedCircularList();
     list.add(new Node(4));
     list.add(new Node(10));
     list.add(new Node(14));
     list.print();

     
     //Adding a node in between.
     list.add(new Node(0));
     list.print();
     list.add(new Node(11));
     list.print();     
  }
  
  
  public void add(Node n)
  {
     if(head.next==head)
     {
     	head.next = n;
     	n.next = head;
     	return;
     }
     
     //find the right pos.
     Node prev = head.next;
     Node cur = head.next.next;
     while(cur!=head && cur.data<=n.data)
     {
     	prev = cur;
		cur = cur.next;
     }
     
     n.next = prev.next;
     prev.next = n;
     if(n.data<prev.data)
     {
        int temp = n.data;
        n.data = prev.data;
        prev.data = temp;
     }     
  }
  
  
  
  
  
  public void print()
  {
     Node n = head.next;
     while(n!=head)
     {
     	System.out.println(n.data);
     	n = n.next;
     }
     System.out.println("******");
  
  }


  static final class Node
  {
  	private Node next;
  	private Integer data;
  	Node(Integer data)
  	{
  		this.data = data;
  	}
  }
}

public class SortedCircularList
{
  //sentinel node.
  private final Node head;
  
  public SortedCircularList()
  {
  	head = new Node(null);
  	head.next = head;
  }
  
  public static void main(String ...args)
  {
     SortedCircularList list = new SortedCircularList();
     list.add(new Node(4));
     list.add(new Node(10));
     list.add(new Node(14));
     list.print();

     
     //Adding a node in between.
     list.add(new Node(0));
     list.print();
     list.add(new Node(11));
     list.print();     
  }
  
  
  public void add(Node n)
  {
     if(head.next==head)
     {
     	head.next = n;
     	n.next = head;
     	return;
     }
     
     //find the right pos.
     Node prev = head.next;
     Node cur = head.next.next;
     while(cur!=head && cur.data<=n.data)
     {
     	prev = cur;
		cur = cur.next;
     }
     
     n.next = prev.next;
     prev.next = n;
     if(n.data<prev.data)
     {
        int temp = n.data;
        n.data = prev.data;
        prev.data = temp;
     }     
  }
  
  
  
  
  
  public void print()
  {
     Node n = head.next;
     while(n!=head)
     {
     	System.out.println(n.data);
     	n = n.next;
     }
     System.out.println("******");
  
  }


  static final class Node
  {
  	private Node next;
  	private Integer data;
  	Node(Integer data)
  	{
  		this.data = data;
  	}
  }

}

public class InsertIntoSortedCircularLL {
public static void main(String args[]){
Node head = Node.createLinkedList();
Node curr =head;
while(curr.next != null)
curr=curr.next;
curr.next=head;
Scanner scan = new Scanner(System.in);
System.out.print("Enter element to insert : ");
int ele = scan.nextInt();
Node n = new Node(ele);
if(ele<=head.data){
n.next=head;
curr.next=n;
}
else{
curr=head;
while(curr.next.data<ele && curr.next!=head)
curr=curr.next;
n.next=curr.next;
curr.next=n;
}
curr=head.next;
System.out.print(head.data);
while(curr!=head){
System.out.print(curr.data);
curr=curr.next;
}
}

}