C++链表排序算法题解析 |21xrx.com

C++链表排序算法题解析

2023-07-08 22:03:47 深夜i -- --

C++ 链表排序算法解析

链表是一种常用的数据结构，在C++编程中经常用到。链表排序算法就是对链表中的数据元素按照一定的规则进行排序。常见的排序算法有冒泡排序、快速排序、插入排序和归并排序等，这里介绍一下归并排序的链表实现方法。

归并排序的链表实现

归并排序是将待排序的序列不断拆分成小的子序列，然后再将子序列合并成有序的序列。链表排序也是一样，把链表不断拆分成小的链表，然后再将小的链表合并成有序的链表。具体实现思路如下：

1. 首先定义一个辅助函数 merge(ListNode* l1, ListNode* l2)，用于合并两个有序链表。具体实现思路如下：

定义一个新的链表头节点 dummy，作为合并后链表的头节点。

比较 l1 和 l2 的节点值，将较小的节点添加到 dummy 链表的末尾，并继续比较两个链表的下一个节点。

当其中一个链表为空时，直接将另外一个链表剩余的节点添加到 dummy 链表的末尾即可。

最后返回 dummy 链表的头节点。

2. 接下来就是归并排序的主函数 sortList(ListNode* head)。具体实现思路如下：

首先找到链表的中点，可以使用快慢指针的方式。将链表从中点分成两个链表。

对两个链表进行递归调用 sortList()，直到链表长度为 1。

将两个有序链表合并成一个有序链表，返回合并后的链表头节点。

参考代码

struct ListNode {

int val;

ListNode* next;

ListNode(int x) : val(x), next(nullptr) {}

};

class Solution {

public:

ListNode* sortList(ListNode* head) {

if (!head || !head->next) return head;

ListNode* slow = head;

ListNode* fast = head->next;

while (fast && fast->next)

slow = slow->next;

fast = fast->next->next;

ListNode* tmp = slow->next;

slow->next = nullptr;

ListNode* l1 = sortList(head);

ListNode* l2 = sortList(tmp);

return merge(l1, l2);

}

ListNode* merge(ListNode* l1, ListNode* l2) {

ListNode* dummy = new ListNode(-1);

ListNode* cur = dummy;

while (l1 && l2) {

if (l1->val <= l2->val)

cur->next = l1;

l1 = l1->next;

else

cur->next = l2;

l2 = l2->next;

cur = cur->next;

}

cur->next = l1 ? l1 : l2;

return dummy->next;

}

};

总结

归并排序是一种很稳定、时间复杂度为 O(nlogn) 的排序算法，能够满足链表排序的要求。而且在链表排序中，归并排序的常数因子比快速排序小，性能要更优。因此，在 C++ 链表排序算法中，归并排序是一种很好的选择。希望本篇文章对大家学习 C++ 链表排序算法有所帮助。

上一篇: idea打包java可执行jar包

下一篇: "C++相比C语言更高效的原因"

评论区

()

相似文章