给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
示例 1：
1
2
| 输入：head = [4,2,1,3]
输出：[1,2,3,4]
|
示例 2：
1
2
| 输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]
|
示例 3：
题目大意
给定链表的头节点 head，要求将链表按升序排列并返回排序后的链表头节点。
解题思路
对于链表排序，最适合的高效算法是归并排序，原因如下：
- 归并排序的时间复杂度为 O (n log n)，是链表排序的最优选择
- 链表的归并操作不需要像数组那样额外分配 O (n) 的空间
- 链表的中点查找可以通过快慢指针高效实现
归并排序的核心步骤：
- 分解：使快慢指针找到链表中点，将链表分成两部分
- 递归：对左右两部分分别进行排序
- 合并：将两个已排序的链表合并成一个有序链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
| class Solution {
public:
ListNode* sortList(ListNode* head) {
// 边界条件：空链表或只有一个节点，直接返回
if (head == nullptr || head->next == nullptr) {
return head;
}
// 1. 找到链表中点，将链表分成两部分
ListNode* mid = findMiddle(head);
ListNode* rightHead = mid->next;
mid->next = nullptr; // 切断链表
// 2. 递归排序左右两部分
ListNode* left = sortList(head);
ListNode* right = sortList(rightHead);
// 3. 合并两个已排序的链表
return merge(left, right);
}
private:
// 找到链表的中点（使用快慢指针）
ListNode* findMiddle(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return head;
}
ListNode* slow = head;
ListNode* fast = head->next; // 快指针超前一步，确保中点在左半部分
while (fast != nullptr && fast->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
// 合并两个已排序的链表
ListNode* merge(ListNode* l1, ListNode* l2) {
// 创建虚拟头节点，简化合并操作
ListNode* dummy = new ListNode(0);
ListNode* curr = dummy;
// 合并两个链表
while (l1 != nullptr && l2 != nullptr) {
if (l1->val < l2->val) {
curr->next = l1;
l1 = l1->next;
} else {
curr->next = l2;
l2 = l2->next;
}
curr = curr->next;
}
// 处理剩余节点
curr->next = (l1 != nullptr) ? l1 : l2;
// 保存结果并释放虚拟节点
ListNode* result = dummy->next;
delete dummy;
return result;
}
};
|
