1. 引言
链表(Linked List)是一种常见的数据结构,支持动态内存分配,适用于插入和删除操作频繁的场景。而排序(Sorting)是计算机科学中的重要算法之一,不同的排序算法适用于不同的数据结构。本篇文章将介绍 链表的基本概念、常见排序算法 以及 如何对链表进行排序。
2. 链表基础
2.1 链表的定义
链表由一系列节点(Node)组成,每个节点包含两部分:
val
:存储数据。next
:指向下一个节点的指针。
单链表(Singly Linked List)的基本结构如下:
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
双向链表(Doubly Linked List)还包含 prev
指针,指向前一个节点。
3. 链表排序的常见方法
对链表进行排序的常见方法包括:
- 归并排序(Merge Sort) - 适用于链表,时间复杂度 O(n log n)。
- 快速排序(Quick Sort) - 可用于链表,但需要额外优化。
- 插入排序(Insertion Sort) - 适用于部分有序链表,时间复杂度 O(n²)。
- 冒泡排序(Bubble Sort) - 不适用于链表,时间复杂度 O(n²)。
我们主要讨论适用于链表的 归并排序 和 插入排序。
4. 归并排序(Merge Sort)
4.1 归并排序的思想
归并排序基于 分治法(Divide and Conquer):
- 分割(Divide): 将链表从中间拆分为两个子链表。
- 排序(Sort): 递归地对两个子链表进行排序。
- 合并(Merge): 使用 合并两个有序链表 的方法,将两个子链表合并成一个有序链表。
4.2 代码实现
class Solution {
public:
ListNode* sortList(ListNode* head) {
if (!head || !head->next) return head;
// 使用快慢指针找到链表的中点
ListNode* slow = head, *fast = head->next;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
ListNode* mid = slow->next;
slow->next = nullptr; // 断开链表
ListNode* left = sortList(head);
ListNode* right = sortList(mid);
return merge(left, right);
}
private:
ListNode* merge(ListNode* l1, ListNode* l2) {
ListNode dummy(0), *tail = &dummy;
while (l1 && l2) {
if (l1->val < l2->val) {
tail->next = l1;
l1 = l1->next;
} else {
tail->next = l2;
l2 = l2->next;
}
tail = tail->next;
}
tail->next = l1 ? l1 : l2;
return dummy.next;
}
};
4.3 复杂度分析
- 时间复杂度: O(n log n)
- 空间复杂度: O(log n)(递归栈)
5. 插入排序(Insertion Sort)
5.1 插入排序的思想
插入排序适用于部分有序的链表。基本思想:
- 维护一个有序链表部分,逐个插入未排序部分的节点。
- 采用 哨兵节点 简化插入逻辑。
5.2 代码实现
class Solution {
public:
ListNode* insertionSortList(ListNode* head) {
if (!head || !head->next) return head;
ListNode dummy(0);
ListNode* pre = &dummy;
dummy.next = head;
ListNode* cur = head;
while (cur->next) {
if (cur->next->val >= cur->val) {
cur = cur->next;
continue;
}
ListNode* temp = cur->next;
cur->next = temp->next;
pre = &dummy;
while (pre->next->val < temp->val) {
pre = pre->next;
}
temp->next = pre->next;
pre->next = temp;
}
return dummy.next;
}
};
5.3 复杂度分析
- 时间复杂度: O(n²)
- 空间复杂度: O(1)
6. 总结
排序算法 | 时间复杂度 | 适用场景 |
---|---|---|
归并排序 | O(n log n) | 适用于任何链表 |
快速排序 | O(n log n) | 不太适合链表(需要额外优化) |
插入排序 | O(n²) | 适用于部分有序链表 |
冒泡排序 | O(n²) | 不推荐 |
选用建议
- 若链表长度较大,推荐 归并排序。
- 若链表大部分已经有序,可选择 插入排序。
以上是关于 链表排序 的详细解析,希望对你有所帮助!