148. 排序链表
4 min
题目
解法：归并排序
思路
使用归并排序（分治法）对链表进行排序。通过快慢指针找到链表中点并分割，递归排序左右两部分后合并。
该方法正确性基于数学归纳法：当链表长度为0或1时自然有序；假设长度小于n的链表可排序，则对长度n的链表，分割后递归排序得到两个有序子链表，合并操作保持有序性，因此整个链表有序。
- Step 1: 递归终止条件判断，若链表为空或只有一个节点则直接返回
- Step 2: 使用快慢指针找到中点，并用prev指针记录中点前驱，将链表从中点断开
- Step 3: 递归调用sortList分别排序左右两部分链表
- Step 4: 调用merge函数合并两个已排序的子链表，返回合并后的头节点
复杂度
- 时间复杂度:
- 空间复杂度:
代码
class Solution {
public:
ListNode* sortList(ListNode* head) {
// 1. 递归终止条件
if (head == nullptr || head->next == nullptr) {
return head;
}
// 2. 找到中点并切断 (快慢指针)
ListNode* prev = nullptr;
ListNode* slow = head;
ListNode* fast = head;
while (fast != nullptr && fast->next != nullptr) {
prev = slow;
slow = slow->next;
fast = fast->next->next;
}
// 将链表从中点断开
prev->next = nullptr;
// 3. 递归排序左右两部分
ListNode* left = sortList(head);
ListNode* right = sortList(slow);
class Solution {
public:
ListNode* sortList(ListNode* head) {
// 1. 递归终止条件
if (head == nullptr || head->next == nullptr) {
return head;
}
// 2. 找到中点并切断 (快慢指针)
ListNode* prev = nullptr;
ListNode* slow = head;
ListNode* fast = head;
while (fast != nullptr && fast->next != nullptr) {
prev = slow;
slow = slow->next;
fast = fast->next->next;
}
// 将链表从中点断开
prev->next = nullptr;
// 3. 递归排序左右两部分
ListNode* left = sortList(head);
ListNode* right = sortList(slow);
// 4. 合并有序链表
return merge(left, right);
}
private:
// 合并两个有序链表的辅助函数
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;
}
// 如果有一个链表还没走完，直接连接
if (l1 != nullptr) curr->next = l1;
if (l2 != nullptr) curr->next = l2;
ListNode* head = dummy->next;
delete dummy; // 释放内存
return head;
}
};