题目链接

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

题目描述

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

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

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

• 0<=NumberofNodes<=5∗1040 <= Number of Nodes <= 5 * 10^40<=NumberofNodes<=5∗104
• −106<=Node.val<=106-10^6 <= Node.val <= 10^6−106<=Node.val<=106
• −106<=insertVal<=106- 10^6 <= insertVal <= 10^6−106<=insertVal<=106

解法：分类讨论

第一种情况：head为空，这时需要新建一个结点指向自己。

第二种情况：存在 insertVal >= cur.val and insertVal <= cur.next.val，insertVal 就直接插入到 cur和 cur.next之间。

第三种情况：insertVal >= 链表中结点的最大值或者 insertVal <= 链表中结点的最小值，那么insertVal 就插入链表中最大结点和最小结点之间。

第四种情况：原链表中所有结点值都相同。此时insertVal 插入任何一个位置都可以。cur最初指向 head，如果它再次来到了 head，说明链表中的结点都一样。

时间复杂度： O(n)O(n)O(n) nnn 是链表中的结点数量

C++代码：

/*
// 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) {//第一种情况 head 为空if(head == nullptr){Node * node = new Node(insertVal);node->next = node;return node;}Node * cur = head;//如果cur 再次来到head 说明链表中结点值都相同 即第四种情况while(cur->next != head){//第二种情况if(insertVal >= cur->val && insertVal <= cur->next->val) break;//第三种情况if(cur->val > cur->next->val && (insertVal >= cur->val || insertVal <= cur->next->val)) break;cur = cur->next;}//统一插入新节点 insertValNode * node = new Node(insertVal);node->next = cur->next;cur->next = node;return head;}
};

Python代码：

"""
# Definition for a Node.
class Node:def __init__(self, val=None, next=None):self.val = valself.next = next
"""class Solution:def insert(self, head: 'Node', insertVal: int) -> 'Node':if head == None:node =  Node(insertVal)node.next = nodereturn nodecur = headwhile cur.next != head:if insertVal >= cur.val and insertVal <= cur.next.val:breakif cur.val > cur.next.val and (insertVal >= cur.val or insertVal <= cur.next.val):breakcur = cur.nextnode =  Node(insertVal)node.next = cur.nextcur.next = nodereturn head