数据结构
网络
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 次浏览
广告