This is [029, sorted circular linked list] on LeetCode. The difficulty is [medium]

subject

Given a point in a cyclic monotone non decreasing list, write a function to insert a new element insertVal into the list so that the list is still cyclic ascending.

A given can be a pointer to any vertex in the list, not necessarily to the smallest element in the list.

If there are multiple insertion positions that meet the conditions, you can select any position to insert a new value, and the whole list remains orderly after insertion.

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 the originally given node.

Example:

Input: head = [3,4,1], insertVal = 2
 Output:[3,4,1,2]
Explanation: in the above figure, there is a loop sequence table with three elements. You get the finger of the node with the value of 3
 Needle, we need to insert element 2 into the table. The newly inserted node should be between 1 and 3. After insertion, the whole
 A list is shown in the figure below. Finally, node 3 is returned.

Problem solution

In order to make the circular linked list of the inserted new node still sort, the value of the previous node of the new node should be smaller than that of the new node, and the value of the latter node should be larger than that of the new node, but there are two special cases to deal with

• If the value of the new node is greater than the existing maximum value in the linked list, it is greater than the value of its previous node (maximum value) and greater than the value of the next node (minimum value)
• If the value of the new node is smaller than the existing minimum value in the linked list, it is less than the value of its previous node (maximum value) and less than the value of the next node (minimum value)

To sum up, in both cases, new nodes are inserted between the maximum and minimum values

Therefore, you need to traverse the circular linked list and judge each time you find two adjacent nodes. There are three cases

If two adjacent nodes cannot be found (the circular linked list is empty or the circular linked list has only one node)

• When the circular linked list is empty, the new node is inserted into the circular linked list, and the new node points to itself
• When the circular linked list has only one node, let the original node of the circular linked list point to the new node and the new node point to the original node

If the value of the former node is smaller than the value inserted by the generation, and the value of the latter node is larger than the value inserted by the generation, the new node is inserted between the two nodes

If two qualified nodes cannot be found, that is, the value to be inserted is greater than the existing maximum value or less than the existing minimum value in the linked list, the new node will be inserted between the maximum value and the minimum value

code implementation

class Solution {

     public Node insert(Node head, int insertVal) {
        // Create a new node with the inserted value
        Node newNode = new Node(insertVal);
        // When the circular linked list is empty
        if (head == null) {
            // The new node is the head node and the only node
            head = newNode;
            // The new node points to itself
            head.next = head;
        // When the circular linked list has only one node
        } else if (head.next == null) {
            // The original node points to the new node
            head.next = newNode;
            // The new node points to the original node
            newNode.next = head;
        // When the cyclic list is greater than or equal to two nodes
        } else {
            insertCore(head, newNode);
        }
        return head;
    }

    public void insertCore(Node head, Node newNode) {
        // When traversing, the current node is initially the head node
        Node currNode = head;
        // When traversing, the next node of the current node is initially the next node of the head node
        Node nextNode = head.next;
        // The node that records the maximum value of the circular linked list, initially the head node
        Node maxNode = head;
       /* Traversing the loop linked list, the loop termination conditions are divided into two cases
       * If the value of the current node is less than the value of the new node and the value of the next node of the current node is greater than the value of the new node, the cycle ends
       * If the next node of the current node is the head node, it indicates that the linked list has been traversed and the cycle ends*/
        while (!(currNode.val <= newNode.val && nextNode.val >= newNode.val) && nextNode != head) {
            // Reset the current node and make the next node of the current node as the current node
            currNode = nextNode;
            // Reset the next node of the current node and make the next node of the next node of the current node the next node of the current node
            nextNode = nextNode.next;
            /* Since the node of the maximum value is initially the head node, and the head node is not necessarily the smallest, the tail node of the circular linked list is not necessarily the largest
            * Therefore, you need to compare the size of the current node and the maximum node every time*/
            if (currNode.val >= maxNode.val) {
                maxNode = currNode;
            }
        }
        // In the first case of loop termination, the value of the current node is less than that of the new node, and the value of the next node of the current node is greater than that of the new node
        if (currNode.val <= newNode.val && nextNode.val >= newNode.val) {
            // The current node points to the new node
            currNode.next = newNode;
            // The new node points to the next node of the current node
            newNode.next = nextNode;
        /* In the second case of loop termination, two adjacent nodes satisfying the relationship cannot be found after traversing the linked list,
            That is, the value of the new node is larger than the maximum value or smaller than the minimum value*/
        } else {
            // The new node points to the next node of the maximum node
            newNode.next = maxNode.next;
            // The node with the maximum value points to the new node
            maxNode.next = newNode;
        }
    }
}

Complexity analysis

Suppose the number of nodes in the circular linked list is n

Time complexity:

The linked list needs to be traversed, so the time complexity is O(n)

Space complexity:

Only a few nodes are declared, so the space complexity is O(1)