Insert into a Cyclic Sorted List

LintCode LinkedList

这道题要向一个环形有序列表里面插入一个node,要满足插入后的List仍然有序。
我一开始不停地尝试curt, prev node怎么变化才能找到insert的位置，困于找得到newNode.next但不知道newNode前面的node怎么表示。然后却不懂得跳出来先从整体上看有哪些可能的位置可以插入。
实际上只有两种位置可以插入：

• 像例子中的3 -> 5之间的位置
• 比如在上面例子中插入6时，5->1中间的位置（或者时在3->5->2中插入1时，5->2中间的位置

从整体上把握了哪些地方可以insert,就可以来遍历节点找到可以插入的地方：

public class Solution {
    /**
     * @param node a list node in the list
     * @param x an integer
     * @return the inserted new list node
     */
    public ListNode insert(ListNode node, int x) {
        // Write your code here
        ListNode newNode = new ListNode(x);
        if (node == null){
            newNode.next = newNode;
            return newNode;
        }
        ListNode curt = node;
        ListNode prev = null;
        do {
            prev = curt;
            curt = curt.next;
            if (prev.val <= curt.val && (prev.val <= x && curt.val >= x)){
               break;
            }
            if (prev.val > curt.val && (x > prev.val || x < curt.val)){
                break;
            }
        } while (curt != node);
        newNode.next = curt;
        prev.next = newNode;
        return curt;
    }
}

while和 do while的区别：

http://www.runoob.com/java/java-loop.html