剑指 Offer II 029. 排序的循环链表

The description of the problem

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

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

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

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

 

来源：力扣（LeetCode）

an example

The codes for this

#include <iostream>
using namespace std;
// Definition for a Node.
class Node {
    
public:
    int val;
    Node* next;

    Node() {
    }

    Node(int _val) {
    
        val = _val;
        next = NULL;
    }

    Node(int _val, Node* _next) {
    
        val = _val;
        next = _next;
    }
};

class Solution {
    
public:
    Node* insert(Node* head, int insertVal) {
    
        // case 1 head == nullptr
        Node *new_node = new Node(insertVal);
        if (head == nullptr) {
    
            new_node->next = new_node;
            return new_node;
        }
        // case 2 there is only one element in the circular loop
        if (head == head->next) {
    
            head->next = new_node;
            new_node->next = head;
            return head;
        }
        // case 3 there are the elements in the circular loop more than 2
        Node *cur_node = head, *next_node = head->next;
        while(next_node != head){
    
            if (insertVal >= cur_node->val &&insertVal <= next_node->val) break;
            if ((cur_node->val > next_node->val) && (insertVal>= cur_node->val || insertVal <= next_node->val)){
    
                break;
            }
            cur_node = next_node;
            next_node = next_node->next;    
        }
        cur_node->next = new_node;
        new_node->next = next_node;
        
        return head;
    }
};
int main()
{
    
    Solution s;
    Node *head = new Node(1);
    head->next = new Node(2);
    head->next->next = new Node(3);
    head->next->next->next = new Node(4);
    head->next->next->next->next = head;
    int insertVal = 5;
    head = s.insert(head, insertVal);
    Node *cur_node = head;
    cout << "insert " << insertVal << " to the list" << endl;
    while (cur_node->next != head) {
    
        cout << cur_node->val << " ";
        cur_node = cur_node->next;
    }
    cout << endl;
    return 0;
}

The corresponding results

$ ./test
insert 5 to the list
1 2 3 4