708. Insert into a Sorted Circular Linked List #

题目 #

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

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

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

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

思路 #

代码 #

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 boolean canInsert (Node head, int insertVal) {
        if (head.val == insertVal) return true;
        if (head.val < insertVal && insertVal < head.next.val) return true;
        if (head.val > head.next.val && head.val < insertVal) return true;
        if (head.val > head.next.val && insertVal < head.next.val) return true;
        return false;
    }
    public Node insert(Node head, int insertVal) {
        if (head == null) {
            Node ring = new Node(insertVal);
            ring.next = ring;
            return ring;
        }
        else {
            Node ptr = head;
            while (ptr.next != head && canInsert(ptr, insertVal) == false) ptr = ptr.next;
            ptr.next = new Node(insertVal, ptr.next);
            return head;
        }
    }