資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
JavaScript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會研究
時尚研究
法律研究插入排序列表 C++
假設我們有一個連結串列，我們需要對這個連結串列進行插入排序。所以，如果連結串列是 [9,45,23,71,80,55]，排序後的連結串列就是 [9,23,45,55,71,80]。
為了解決這個問題，我們將按照以下步驟進行 −
dummy := 具有隨機值的新節點
node := 給定的連結串列
當 node 不為空時，
newNode = node 的下一個，dummyHead := dummy 的下一個，prevDummyHead := dummy
當 true 時 −
如果 dummyHead 不存在，dummyHead 的值大於 node 的值
node 的下一個 := dummyHead
prevDummyHead 的下一個 := node
跳出迴圈
prevDummyHead := dymmyHead，dummyHead = dummy head 的下一個
node := 下一個節點
- 返回 dummy 的下一個
示例
讓我們看看以下實現，以獲得更好的理解 −
class Solution {
public:
ListNode* insertionSortList(ListNode* a) {
ListNode* dummy = new ListNode(-1);
ListNode* node = a;
ListNode* nextNode;
ListNode* dummyHead;
ListNode* prevDummyHead;
while(node != NULL){
nextNode = node->next;
dummyHead = dummy->next;
prevDummyHead = dummy;
while(1){
if(!dummyHead || dummyHead->val > node->val){
node->next = dummyHead;
prevDummyHead->next = node;
//cout << prevDummyHead->val << " " << node->val << endl;
break;
}
}
prevDummyHead = dummyHead;
dummyHead = dummyHead->next;
}
node = nextNode;
}
return dummy->next;
}輸入
[9,45,23,71,80,55]
輸出
[9,23,45,55,71,80]
更新於: 03-2-2020
421 次瀏覽
廣告