Insert into a Cyclic Sorted List

Problem:

 * Given a node from a cyclic linked list which has been sorted, 

 * write a function to insert a value into the list such that it remains a cyclic sorted list. 

 * The given node can be any single node in the list.

Solution:

---

Source Code:

/**
 * Given a node from a cyclic linked list which has been sorted, 
 * write a function to insert a value into the list such that it remains a cyclic sorted list. 
 * The given node can be any single node in the list.
 */

/**
 * @author Antonio081014
 * @since Oct 28, 2013, 10:43:52 AM
 */
public class Test {

 public static void main(String[] args) {
  CycledList list = new CycledList();
  list.print();
  list.insert(3);
  list.print();
  list.insert(1);
  list.insert(1);
  list.print();
 }
}

class CycledList {
 public Node head;

 /**
  * Several Cases:

  * 1st, when linked list is empty; 

  * 2nd, when new element is either minimum or maximum; 

  * 3rd, when new element is in between two sorted elements. 

  * 
  * 
  * Since this list is like a circle, we don't necessary to have the smallest
  * element as the head, but it's definitely sorted.
  * */
 public void insert(int x) {
  // 1st Case;
  if (head == null) {
   head = new Node(x);
   head.next = head;
   return;
  }
  Node p = head;
  Node prev = null;
  do {
   prev = p;
   p = p.next;
   // 2nd Case;
   if (prev.data >= p.data && (x <= p.data || x >= prev.data))
    break;
   // 3rd Case;
   if (prev.data <= x && p.data >= x)
    break;
  } while (p != head);
  Node tmp = new Node(x);
  prev.next = tmp;
  tmp.next = p;
 }

 public void print() {
  if (head == null) {
   System.out.println("Empty Cycled List");
   return;
  }
  Node p = head;
  do {
   System.out.print(p.data + " ");
   p = p.next;
  } while (head != p);
  System.out.println();
 }
}

class Node {
 public int data;
 public Node next;

 public Node(int x) {
  this.data = x;
  next = null;
 }

 public Node(int x, Node n) {
  this.data = x;
  this.next = n;
 }
}