Sword finger offer II 029 Sorted circular linked list

A word summary

Pay attention to various boundary problems , For example, an empty linked list , A linked list of elements , And a linked list with equal values

subject

A point in a monotone nondecreasing list of a given cycle , Write a function to insert a new element into the list insertVal , Make the list still cyclic ascending .

Given can be the pointer to any vertex in the list , Not necessarily a pointer to the smallest element in the list .

If there are multiple insertion positions that meet the conditions , You can choose any location to insert a new value , After insertion, the whole list remains in order .

If the list is empty （ The given node is null）, You need to create a circular sequence table and return this node . otherwise . Please return to the original given node .

link ：https://leetcode.cn/problems/4ueAj6

Ideas

Because it is monotonic and non decreasing , So you can traverse along the incoming header . Of course , Remember the previous node when traversing . When the given value size is between two nodes , Insert a new node .

After all kinds of debugging , I found the most difficult part of the problem , The point is that you have to consider a variety of special scenarios . For example, an empty linked list is given , A linked list with only one element is given , The given value is not between the maximum and minimum values of the linked list . It's exploding .

solution

Code

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;
        }
        //  I ran a lap without success , It means that the values of the linked list are the same , So just plug it in 
        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;
}