单链表插入排序
单链表的插入排序在思路上与顺序表是一致的，它的难点在于如何对链表进行操作，包括链表的插入以及防止访问空节点。只有能够保证思路清晰，写出也是不难的。
#include <bits/stdc++.h>
using namespace std;
node *insertSort(node *head) {
//表空或者只有一个节点 不需要进行排序 直接返回
if (!head || !head->next) return head;
node *dummy = new noed(0);//创建虚拟节点
dummy->next = head;
//将链表分为有序区域和无序区 有序区初始只有一个节点
node *p = dummy->next->next;// p初始指向无序表的第一个节点
dymmy->next->next = NULL;//断链
while (p) {
node *q = p->next; //保存p->next, 因为插入过程可能改变p->next
node *pre = dummy;
//当有序表不到最后一个节点并且有序表的元素小于等于无序表的元素 pre = pre->next
while (pre->next && pre->next->val <= p->val) pre = pre->next;
//插入无序表中此时p指向的节点到有序表中
p->next = pre->next;
pre->next = p
p = q;
}
return dummy->next;
}本文参与?腾讯云自媒体分享计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读