数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究在 C++ 中插入排序循环链表
假设我们有一个来自循环链表的节点，该循环链表按升序排序，我们需要定义一个函数将值 insertVal 插入到列表中，以使其保持为排序的循环链表。
该节点可以是列表中任何单个节点的引用，不一定必须是循环列表的第一个值。如果有多个适合插入的位置，我们可以选择任何位置插入新值。如果列表为空，则必须创建一个新的单个循环列表并返回该单个节点的引用。否则，我们应该返回原始给定的节点。
因此，如果输入类似于 head = [3,4,1]，insertVal = 2，图像，则输出将为 [3,4,1,2]，图像
为了解决这个问题，我们将遵循以下步骤：
如果 head 为空，则：
head := 带有 val 的新节点
head 的 next := head
否则
curr = head 的 next
prev = head
temp = 带有 val 的新节点
done := false
执行无限循环，执行：
如果 curr 中的 val >= val 且 prev 的 val <= val，则：
prev := temp 的 next
temp := curr 的 next
done := true
退出循环
如果 prev 的 val > curr 的 val，则：
如果 prev 的 val <= val 或 val <= curr 的 val，则：
prev := temp 的 next
temp := curr 的 next
done := true
退出循环
如果 curr 与 head 相同，则：
退出循环
prev := curr
curr := curr 的 next
如果 done 为 false，则：
temp := head 的 next
prev := temp 的 next
head := temp
返回 head
示例
让我们看看以下实现以更好地理解：
#include <bits/stdc++.h>
using namespace std;
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 val) {
if(!head){
head = new Node(val);
head->next = head;
}
else{
Node* curr = head->next;
Node* prev = head;
Node* temp = new Node(val);
bool done = false;
while(1){
if (curr->val >= val && prev->val <= val) {
prev->next = temp;
temp->next = curr;
done = true;
break;
}
if (prev->val > curr->val) {
if (prev->val <= val || val <= curr->val) {
prev->next = temp;
temp->next = curr;
done = true;
break;
}
}
if (curr == head)
break;
prev = curr;
curr = curr->next;
}
if(!done){
temp->next = head;
prev->next = temp;
head = temp;
}
}
return head;
}
};
main(){
Solution ob;
Node *head = new Node(3);
head->next = new Node(4);
head->next->next = new Node(1, head);
ob.insert(head, 2);
Node *temp = head;
if (head != NULL){
do{
cout << temp->val << " ";
temp = temp->next;
}
while (temp != head);
}
}输入
node *head = new Node(3); head->next = new Node(4); head->next->next = new Node(1, head); insertVal = 2
输出
3 4 1 2
324 次查看
