029. 排序的循环链表 C++

一时失言乱红尘 2022-09-14 15:17 124阅读 0赞

# 029. 排序的循环链表 #

## 题目说明 ##

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

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

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

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

示例 1：

![在这里插入图片描述][2e55ade9c4cc4620bcb47d0d6c9fd5c1.png]

输入：head = \[3,4,1\], insertVal = 2  
输出：\[3,4,1,2\]  
解释：在上图中，有一个包含三个元素的循环有序列表，你获得值为 3 的节点的指针，我们需要向表中插入元素 2 。新插入的节点应该在 1 和 3 之间，插入之后，整个列表如上图所示，最后返回节点 3 。  
![在这里插入图片描述][2ebe4a541af34016a955362f2d968e0d.png]

示例 2：

输入：head = \[\], insertVal = 1  
输出：\[1\]  
解释：列表为空（给定的节点是 null），创建一个循环有序列表并返回这个节点。  
示例 3：

输入：head = \[1\], insertVal = 0  
输出：\[1,0\]

提示：

0 <= Number of Nodes <= 5 \* 10^4  
\-10^6 <= Node.val <= 10^6  
\-10^6 <= insertVal <= 10^6

## C++解法 ##

1.  链表无节点或者只存在一个节点，则直接新节点即可；
2.  插入的值大于链表中原有的最大值，或者小于链表中原有的最小值，则新节点插入原来值的最大值和最小值之间；
3.  插入的值介于原链表最大值和最小值之间，那么新节点插入点的前一个节点的值应该不大于新节点的值，后一个节点的值应该不小于新节点的值。

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)
        {
            if (head == NULL)
            {
                head = new Node(insertVal);
                head->next = head;
                return head;
            }
            Node *cur = head;
            while (cur->next != head)
            {
                if (cur->next->val < cur->val)
                {
                    if (cur->next->val >= insertVal)
                    {
                        break;
                    }
                    else if (cur->val <= insertVal)
                    {
                        break;
                    }
                }
                else if (cur->next->val >= insertVal && cur->val <= insertVal)
                {
                    break;
                }
    
                cur = cur->next;
            }
            cur->next = new Node(insertVal, cur->next);
    
            return head;
        }
    };

[2e55ade9c4cc4620bcb47d0d6c9fd5c1.png]: /images/20220828/f2979f2a8f0946919fcaf92b45a3e7b0.png
[2ebe4a541af34016a955362f2d968e0d.png]: /images/20220828/0cf810d01c4e4307b17cf4bf3fa899dd.png