Day109 | 灵神 | 148.排序链表 | 归并排序
以下是灵神的题解，笔者认为这题只要可以看懂就好了
两种方法：分治和迭代
前置题目
方法一：归并排序（分治）
- 找到链表的中间结点 head2 的前一个节点，并断开 head2 与其前一个节点的连接。这样我们就把原链表均分成了两段更短的链表
- 分治，递归调用 sortList，分别排序 head（只有前一半）和 head2。
- 排序后，我们得到了两个有序链表，那么合并两个有序链表，得到排序后的链表，返回链表头节点。
class Solution {
// 876. 链表的中间结点（快慢指针）
ListNode* middleNode(ListNode* head) {
ListNode* pre = head;
ListNode* slow = head;
ListNode* fast = head;
while (fast && fast->next) {
pre = slow; // 记录 slow 的前一个节点
slow = slow->next;
fast = fast->next->next;
}
pre->next = nullptr; // 断开 slow 的前一个节点和 slow 的连接
return slow;
}
// 21. 合并两个有序链表（双指针）
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
ListNode dummy; // 用哨兵节点简化代码逻辑
ListNode* cur = &dummy; // cur 指向新链表的末尾
while (list1 && list2) {
if (list1->val < list2->val) {
cur->next = list1; // 把 list1 加到新链表中
list1 = list1->next;
} else { // 注：相等的情况加哪个节点都是可以的
cur->next = list2; // 把 list2 加到新链表中
list2 = list2->next;
}
cur = cur->next;
}
cur->next = list1 ? list1 : list2; // 拼接剩余链表
return dummy.next;
}
public:
ListNode* sortList(ListNode* head) {
// 如果链表为空或者只有一个节点，无需排序
if (head == nullptr || head->next == nullptr) {
return head;
}
// 找到中间节点 head2，并断开 head2 与其前一个节点的连接
// 比如 head=[4,2,1,3]，那么 middleNode 调用结束后 head=[4,2] head2=[1,3]
ListNode* head2 = middleNode(head);
// 分治
head = sortList(head);
head2 = sortList(head2);
// 合并
return mergeTwoLists(head, head2);
}
};
复杂度分析
- 时间复杂度：O(nlogn)，其中 n 是链表长度。递归式 T(n)=2T(n/2)+O(n)，由主定理可得时间复杂度为 O(nlogn)。
- 空间复杂度：O(logn)。递归需要 O(logn) 的栈开销。
方法二：归并排序（迭代）
方法一的归并是自顶向下计算，需要 O(logn) 的递归栈开销。
方法二将其改成自底向上计算，空间复杂度优化成 O(1)。
自底向上的意思是：
- 首先，归并长度为 1 的子链表。例如 [4,2,1,3]，把第一个节点和第二个节点归并，第三个节点和第四个节点归并，得到 [2,4,1,3]。
- 然后，归并长度为 2 的子链表。例如 [2,4,1,3]，把前两个节点和后两个节点归并，得到 [1,2,3,4]。
- 然后，归并长度为 4 的子链表。
- 依此类推，直到归并的长度大于等于链表长度为止，此时链表已经是有序的了。
具体算法：
- 遍历链表，获取链表长度 length。
- 初始化步长 step=1。
- 循环直到 step≥length。
- 每轮循环，从链表头节点开始。
- 分割出两段长为 step 的链表，合并，把合并后的链表插到新链表的末尾。重复该步骤，直到链表遍历完毕。
- 把 step 扩大一倍。回到第 4 步。
class Solution {
// 获取链表长度
int getListLength(ListNode* head) {
int length = 0;
while (head) {
length++;
head = head->next;
}
return length;
}
// 分割链表
// 如果链表长度 <= size，不做任何操作，返回空节点
// 如果链表长度 > size，把链表的前 size 个节点分割出来（断开连接），并返回剩余链表的头节点
ListNode* splitList(ListNode* head, int size) {
// 先找到 next_head 的前一个节点
ListNode* cur = head;
for (int i = 0; i < size - 1 && cur; i++) {
cur = cur->next;
}
// 如果链表长度 <= size
if (cur == nullptr || cur->next == nullptr) {
return nullptr; // 不做任何操作，返回空节点
}
ListNode* next_head = cur->next;
cur->next = nullptr; // 断开 next_head 的前一个节点和 next_head 的连接
return next_head;
}
// 21. 合并两个有序链表（双指针）
// 返回合并后的链表的头节点和尾节点
pair<ListNode*, ListNode*> mergeTwoLists(ListNode* list1, ListNode* list2) {
ListNode dummy; // 用哨兵节点简化代码逻辑
ListNode* cur = &dummy; // cur 指向新链表的末尾
while (list1 && list2) {
if (list1->val < list2->val) {
cur->next = list1; // 把 list1 加到新链表中
list1 = list1->next;
} else { // 注：相等的情况加哪个节点都是可以的
cur->next = list2; // 把 list2 加到新链表中
list2 = list2->next;
}
cur = cur->next;
}
cur->next = list1 ? list1 : list2; // 拼接剩余链表
while (cur->next) {
cur = cur->next;
}
// 循环结束后，cur 是合并后的链表的尾节点
return {dummy.next, cur};
}
public:
ListNode* sortList(ListNode* head) {
int length = getListLength(head); // 获取链表长度
ListNode dummy(0, head); // 用哨兵节点简化代码逻辑
// step 为步长，即参与合并的链表长度
for (int step = 1; step < length; step *= 2) {
ListNode* new_list_tail = &dummy; // 新链表的末尾
ListNode* cur = dummy.next; // 每轮循环的起始节点
while (cur) {
// 从 cur 开始，分割出两段长为 step 的链表，头节点分别为 head1 和 head2
ListNode* head1 = cur;
ListNode* head2 = splitList(head1, step);
cur = splitList(head2, step); // 下一轮循环的起始节点
// 合并两段长为 step 的链表
auto [head, tail] = mergeTwoLists(head1, head2);
// 合并后的头节点 head，插到 new_list_tail 的后面
new_list_tail->next = head;
new_list_tail = tail; // tail 现在是新链表的末尾
}
}
return dummy.next;
}
};
复杂度分析
- 时间复杂度：O(nlogn)，其中 n 是链表长度。
- 空间复杂度：O(1)。