Linked list: orderly circular linked list

subject

https://leetcode-cn.com/problems/4ueAj6/
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 .

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/4ueAj6
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Their thinking

The topic requires inserting nodes into the ordered circular linked list , And the new linked list still conforms to the ordered nature .

Then we need to traverse the circular linked list , Find two nodes , The front node is less than or equal to the node to be inserted , The rear node is greater than or equal to the node to be inserted .

Except for the insertion rules , Various boundary conditions also need to be considered .

1. In the case of only one node
2. Empty node
3. Two nodes matching the insertion rule could not be found , Insert the new node after the largest node .

The specific code is as follows ：

Code

/* // 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) {
    
        Node node = new Node(insertVal);
        if(head == null) {
    
            head = node;
            head.next = head;
        } else if(head.next == head) {
    
            head.next = node;
            node.next = head;
        } else {
    
            insertCore(head, node); 
        }
        return head;
    }

    private void insertCore(Node head, Node node) {
    
        Node cur = head;
        Node next = head.next;
        Node biggest = head;

        // Record the maximum 
        while(!(cur.val <= node.val && node.val <= next.val) && next != head) {
    
            cur = next;
            next = next.next;
            if(biggest.val <= cur.val) {
    
                biggest = cur;
            }
        }
        if(cur.val <= node.val && node.val  <= next.val) {
    
            // Insert node 
            cur.next = node;
            node.next= next;
        } else {
    
            node.next = biggest.next;
             biggest.next = node;
         }
    }
}

summary

This topic examines the nature of circular linked list , You need to pay attention to how to calculate the maximum value of the linked list and how to modify the point of the linked list . Pay attention to the boundary conditions .