当前位置:网站首页>[Offer29] 排序的循环链表
[Offer29] 排序的循环链表
2022-07-06 09:17:00 【劲腰傩舞】
题目概要:给你一个数,要求你把数据插入一个排序好的循环链表中,使得最终的链表升序。
大致思路:分清楚链表的三种情况:空链表、无最大最小值的链表、有最大最小值的链表。依次对三种情况进行处理。
题目
给定循环单调非递减列表中的一个点,写一个函数向这个列表中插入一个新元素 insertVal ,使这个列表仍然是循环升序的。
给定的可以是这个列表中任意一个顶点的指针,并不一定是这个列表中最小元素的指针。
如果有多个满足条件的插入位置,可以选择任意一个位置插入新的值,插入后整个列表仍然保持有序。
如果列表为空(给定的节点是 null),需要创建一个循环有序列表并返回这个节点。否则。请返回原先给定的节点。
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/4ueAj6
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
输出示例
输入:head = [3,4,1], insertVal = 2
输出:[3,4,1,2]
输入:head = [], insertVal = 1
输出:[1]
解释:列表为空(给定的节点是 null),创建一个循环有序列表并返回这个节点。
输入:head = [1], insertVal = 0
输出:[1,0]
class Solution {
public:
Node* insert(Node* head, int insertVal) {
/*先处理空链表的情况*/
if (!head) {
/*只有一个结点的循环链表。指向自己*/
head = new Node(insertVal);
head->next = head;
return head;
}
/*使用另外一个指针进行遍历,因为最终还需要返回head*/
Node* cur = head;
/*循环条件用来排除链表中没有最大值最小值的情况:只有一个结点。或者所有结点的值相同*/
while(cur->next!=head){
/*并列情况一:插入值在前后两个数的大小之间*/
if (cur->val <= insertVal && insertVal<=cur->next->val)
break;
/*并列情况二:插入值大于链表最大值(第二个条件证明了链表中最大值的存在)*/
else if (cur->val <= insertVal && cur->next->val < cur->val)
break;
/*并列情况三:插入值小于链表最小值(第二个条件证明了链表中最小值的存在)*/
else if (cur->next->val >= insertVal && cur->next->val < cur->val)
break;
cur = cur->next;
}
/*循环完毕。在当前指针之后直接插入 *声明的结点就别用局部变量了。到函数之外就失效了*/
cur->next = new Node(insertVal, cur->next);
/*返回所要求的指针*/
return head;
}
};
边栏推荐
- MySQL時間、時區、自動填充0的問題
- Pat 1097 duplication on a linked list (25 points)
- 程序员老鸟都会搞错的问题 C语言基础 指针和数组
- ESP8266通过Arduino IDE连接Onenet云平台(MQTT)
- Programmers can make mistakes. Basic pointers and arrays of C language
- C language callback function [C language]
- (一)R语言入门指南——数据分析的第一步
- Basic operations of databases and tables ----- view data tables
- ESP学习问题记录
- 荣耀Magic 3Pro 充电架构分析
猜你喜欢
Detailed explanation of Union [C language]
[golang] leetcode intermediate - fill in the next right node pointer of each node & the k-smallest element in the binary search tree
记一次云服务器被密码爆破的经历——关小黑屋、改密码、改端口
Several declarations about pointers [C language]
Priority inversion and deadlock
Characteristics, task status and startup of UCOS III
Redis based distributed locks and ultra detailed improvement ideas
基於Redis的分布式ID生成器
Cannot change version of project facet Dynamic Web Module to 2.3.
Stm32f1+bc20+mqtt+freertos system is connected to Alibaba cloud to transmit temperature and humidity and control LED lights
随机推荐
关于Gateway中使用@Controller的问题
ARM PC=PC+8 最便于理解的阐述
arduino获取随机数
@The difference between Autowired and @resource
STM32 how to locate the code segment that causes hard fault
Redis based distributed ID generator
Oppo vooc fast charging circuit and protocol
RT thread API reference manual
OSPF message details - LSA overview
ESP8266连接onenet(旧版MQTT方式)
Cannot change version of project facet Dynamic Web Module to 2.3.
CUDA C programming authoritative guide Grossman Chapter 4 global memory
Kaggle competition two Sigma connect: rental listing inquiries (xgboost)
MySQL占用内存过大解决方案
【ESP32学习-1】Arduino ESP32开发环境搭建
Bubble sort [C language]
Programmers can make mistakes. Basic pointers and arrays of C language
Problèmes avec MySQL time, fuseau horaire, remplissage automatique 0
Pat 1097 duplication on a linked list (25 points)
Navigator object (determine browser type)