剑指 Offer II 029. 排序的循环链表

剑指 Offer II 029. 排序的循环链表

【分析】因为插入后链表仍然有序，所以我们遍历链表，找到第一个比要插入的元素大的节点，把这个元素插在这个节点前面就可以了，加下来就是一些细节问题了。

1.首先因为要返回head，所以我们先弄个标记存一下head，令Node dummy = head，然后head当游标来用。

2.因为要插在一个节点前面，所以需要这个节点的前一个节点，因为题目中只给了head，所以我们没法知道head的pre，于是直接把head当pre，head的next来当head即可。

3.但是如果我们一开始的元素就已经比要插入的元素大很多了，比如5,7,0,2，插入1，我们发现我们定的head 7(原head5的next7)已经是大于1的了，但是1不应该插在7的前面。所以这种情况下我们需要找到链表最小的头，我们发现头0有一个特点就是他的pre要>head，但是呢也不排除3,3,3,3这种情况，所以还要判断一下是不是又回到了dummy。

4.链表为空和链表只有一个节点的情况需要额外注意一下子。

几个特殊样例：

[3,3,5]
0
[1]
0
[1]
2
[3,3,3]
0
[]
1

/*
// Definition for a Node.
class Node {
    public int val;
    public Node next;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _next) {
        val = _val;
        next = _next;
    }
};
*/

class Solution {
    public Node insert(Node head, int insertVal) {
        if(head == null){
            Node node =  new Node(insertVal);
            node.next = node;
            return node;
        }
        Node dummy = head;
        Node pre = dummy;
        head = head.next;
        if(insertVal < head.val){
            while(pre.val <= head.val && head != dummy){
                head = head.next; pre = pre.next;
            }
        }
        while(true){
            if(head.val > insertVal) break;
            head = head.next;
            pre = pre.next;
            if(pre.val > head.val) break;
            if(pre == dummy) break;
        }
        pre.next = new Node(insertVal, head);
        return dummy;
    }
}