【单链表】05 有一个带头结点的单链表L,设计一个算法使其元素递增有序。

🕺作者： 主页

我的专栏
C语言从0到1
探秘C++
数据结构从0到1
探秘Linux
算法题上机准备

😘欢迎 ❤️关注 👍点赞 🙌收藏 ✍️留言

题目

有一个带头结点的单链表L,设计一个算法使其元素递增有序。

算法思路

解决办法有很多，如果只考虑链表的形式，所以是以下思路

• 将整个链表分为两段链表，前一段链表是头节点和第一个节点，后一段链表是剩余节点
• 后段链表作为类似参数的形式以插入的方式遍历比较插入前段链表

题解

void sortListAsc(LinkedList& L) {//如果链表为空，或者链表只有一个结点直接返回不需要排序if (L->next == NULL || L->next->next == NULL) {return;}//从第二个结点开始LNode* p = L->next->next;L->next->next = NULL;while (p != NULL) {LNode* next = p->next; //记录一下p的后继防止断链LNode* head = L->next; //head作为每次已排好序的部分链表中的首节点同时作为遍历指针LNode* pre = L; //遍历指针head的前一个结点while (head != NULL && p->data > head->data) {//如果不满足插入位置pre和head后移pre = pre->next;head = head->next;}p->next = head; //在head和pre之间插入ppre->next = p;p = next;//p后移重新遍历未进行排序的结点操作}
}