資料結構
網路
關係資料庫管理系統
作業系統
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 次檢視
