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

一句话概要

注意各种边界问题，比如空链表，一个元素的链表，以及值都相等的链表

题目

给定循环单调非递减列表中的一个点，写一个函数向这个列表中插入一个新元素 insertVal ，使这个列表仍然是循环升序的。

给定的可以是这个列表中任意一个顶点的指针，并不一定是这个列表中最小元素的指针。

如果有多个满足条件的插入位置，可以选择任意一个位置插入新的值，插入后整个列表仍然保持有序。

如果列表为空（给定的节点是 null），需要创建一个循环有序列表并返回这个节点。否则。请返回原先给定的节点。

链接：https://leetcode.cn/problems/4ueAj6

思路

因为是单调非递减，所以沿着传入的头一直往前遍历即可。当然，遍历的时候要记住前一个节点。当给定的值大小在两个节点之间时，插入新节点即可。

经过各种调试，我发现这道题最难的地方，在于你要考虑多种特殊场景。比如给了一个空链表，给了一个只有一个元素的链表，给定的值不在链表最大最小值之间等等情况。简直爆炸。

解法

代码

public Node insert(Node head, int insertVal) {
    
    if (head == null) {
    
        head = new Node(insertVal);
        head.next = head;
        return head;
    }
    if (head.next == head) {
    
        Node node = new Node(insertVal);
        head.next = node;
        node.next = head;
        return head;
    }
    Node current = head.next;
    Node pre = head;
    boolean isRound = false;
    while (true) {
    
        if ((pre.val <= insertVal && current.val >= insertVal) ||
                (pre.val > current.val && (pre.val < insertVal || current.val > insertVal))) {
    
            Node node = new Node(insertVal);
            pre.next = node;
            node.next = current;
            break;
        }
        // 跑了一圈都没有插入成功，说明这个链表的值都一样，因此随便插进去就行
        if (pre == head) {
    
            if (isRound) {
    
                Node node = new Node(insertVal);
                pre.next = node;
                node.next = current;
                break;
            }
            isRound = true;
        }
        current = current.next;
        pre = pre.next;
    }

    return head;
}