当前位置:网站首页>[offer29] sorted circular linked list
[offer29] sorted circular linked list
2022-07-06 12:24:00 【Vigorous waist Nuo dance】
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;
}
};
边栏推荐
- Rough analysis of map file
- ORA-02030: can only select from fixed tables/views
- ARM PC=PC+8 最便于理解的阐述
- Minio文件下载问题——inputstream:closed
- About using @controller in gateway
- 记一次云服务器被密码爆破的经历——关小黑屋、改密码、改端口
- Missing value filling in data analysis (focus on multiple interpolation method, miseforest)
- Kconfig Kbuild
- AMBA、AHB、APB、AXI的理解
- JS變量類型以及常用類型轉換
猜你喜欢
js 变量作用域和函数的学习笔记
Programmers can make mistakes. Basic pointers and arrays of C language
(4) Data visualization of R language -- matrix chart, histogram, pie chart, scatter chart, linear regression and strip chart
JS数组常用方法的分类、理解和运用
Pat 1097 duplication on a linked list (25 points)
JS 函数提升和var变量的声明提升
MySQL takes up too much memory solution
Conditional probability
RT thread API reference manual
(3) Introduction to bioinformatics of R language - function, data Frame, simple DNA reading and analysis
随机推荐
Symbolic representation of functions in deep learning papers
Several declarations about pointers [C language]
STM32 how to locate the code segment that causes hard fault
Classification, understanding and application of common methods of JS array
A possible cause and solution of "stuck" main thread of RT thread
Pytorch four commonly used optimizer tests
[Nodejs] 20. Koa2 onion ring model ----- code demonstration
单片机蓝牙无线烧录
[Offer29] 排序的循环链表
嵌入式启动流程
Cannot change version of project facet Dynamic Web Module to 2.3.
C language callback function [C language]
[Offer18]删除链表的节点
JS variable types and common type conversions
Mysqldump error1066 error solution
The first simple case of GNN: Cora classification
gcc 编译选项
编译原理:源程序的预处理及词法分析程序的设计与实现(含代码)
Feature of sklearn_ extraction. text. CountVectorizer / TfidVectorizer
JS Title: input array, exchange the largest with the first element, exchange the smallest with the last element, and output array.