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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public Node insert(Node head, int insertVal) {
        if (head == null) {
            head = new Node(insertVal);
            head.next = head;
            return head;
        }

        Node curr = head;
        while (!(curr.val <= insertVal && insertVal <= curr.next.val)) {
            // 不满足递增插入条件则继续尝试寻找插入点
            curr = curr.next; // 注意此处先走一步，可便于后续判断是否走了一个环
            if (curr == head || (curr.val > curr.next.val && (insertVal >= curr.val || insertVal <= curr.next.val))) {
                // 如果此时走了一个环，说明全部值相等，在任意位置插入即可
                // 如果在边界处可插入，则在边界处插入
                break;
            }
        }
        curr.next = new Node(insertVal, curr.next);
        return head;
    }
}

References

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