[offer29] sorted circular linked list

Topic summary ： Give you a number , You are required to insert the data into a sorted circular linked list , Make the final linked list ascending .
General train of thought ： Distinguish the three situations of the linked list ： Empty list 、 Linked list without maximum or minimum value 、 Linked list with maximum and minimum values . Deal with the three situations in turn .

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 .

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

Output example

Input ：head = [3,4,1], insertVal = 2
Output ：[3,4,1,2]

Input ：head = [], insertVal = 1
Output ：[1]
explain ： The list is empty. （ The given node is null）, Create a circular sequence table and return this node .

Input ：head = [1], insertVal = 0
Output ：[1,0]

class Solution {
    
public:
    Node* insert(Node* head, int insertVal) {
    
		/* First deal with the empty linked list */
		if (!head) {
    
			/* Circular linked list with only one node . Point to your */
			head = new Node(insertVal);
			head->next = head;
			return head;
		}

		/* Use another pointer to traverse , Because eventually you need to return head*/
		Node* cur = head;

		/* The cycle condition is used to exclude the case that there is no maximum or minimum value in the linked list ： There is only one node . Or the values of all nodes are the same */
		while(cur->next!=head){
    
			/* Juxtaposition case 1 ： The insertion value is between the size of the previous and subsequent numbers */
			if (cur->val <= insertVal && insertVal<=cur->next->val)
				break;
			/* Juxtaposition II ： The insertion value is greater than the maximum value of the linked list ( The second condition proves the existence of the maximum value in the linked list ）*/
			else if (cur->val <= insertVal && cur->next->val < cur->val)
				break;
			/* Parallel case 3 ： The insertion value is less than the minimum value of the linked list ( The second condition proves the existence of the minimum value in the linked list ）*/
			else if (cur->next->val >= insertVal && cur->next->val < cur->val)
				break;
			cur = cur->next;
		}

		/* Cycle is completed . Insert directly after the current pointer  * Don't use local variables for declared nodes . Outside the function, it fails */
		cur->next = new Node(insertVal, cur->next);
		
		/* Return the required pointer */
		return head;

    }
};