599.Insert into a Cyclic Sorted List

1.Description(Easy)

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. Return the inserted new node.

Notice

3->5->1is a cyclic list, so3is next node of1. 3->5->1is same with5->1->3

Example

Given a list, and insert a value4: 3->5->1 Return5->1->3->4

2.Code

Following are the 3 cases to consider

1) prev→val ≤ x ≤ current→val:

Insert between prev and current.

2) x is the maximum or minimum value in the list:

Insert before the head. (ie, the head has the smallest value and its prev→val > head→val.

3) Traverses back to the starting point:

Insert before the starting point.

 public ListNode insert(ListNode node, int x) {
     if(node==null){
            node=new ListNode(x);
            node.next=node;
            return node;

        }
        ListNode current=node;
        ListNode prev=null;
        do{
            prev=current;
            current=current.next;
            if(x<=current.val && x>=prev.val){ //for case 1
                break;
            }
            if((prev.val>current.val)&&(x<current.val || x>prev.val)){//for case 2
                break;
            }

        }while(current!=node);//for case 3

        ListNode newnode=new ListNode(x);
        newnode.next=current;
        prev.next=newnode;
        return newnode;
    }