148. 排序链表
一句话套路归并:快慢找中 + 递归 + 合并两链
题目描述
给你链表的头结点 head ,请将其按 升序 排列并返回 排序后的链表 。
示例 1:
输入:head = [4,2,1,3] 输出:[1,2,3,4]
示例 2:
输入:head = [-1,5,3,4,0] 输出:[-1,0,3,4,5]
示例 3:
输入:head = [] 输出:[]
提示:
- 链表中节点的数目在范围
[0, 5 * 104]内 -105 <= Node.val <= 105
进阶:你可以在 O(n log n) 时间复杂度和常数级空间复杂度下,对链表进行排序吗?
思路
时间
O(n log n)思路
自顶向下归并。快慢指针切两半 -> 递归排序 -> 合并(Q21)。
链表归并的优势
不需要像数组那样开额外临时空间,天然 O(1) 合并。
进阶
自底向上按 size=1,2,4... 倍增归并,可做真 O(1) 空间(面试官常追问)。
快排在链表上最坏会退化,堆排序不方便,所以这题的标准答案是归并。
图解
链表结构(来自本仓库测试数据)
C++17 题解
namespace lc0148 {
class Solution {
public:
ListNode* sortList(ListNode* head) {
if (!head || !head->next) return head;
// 找左半部分的尾:fast 从 head->next 出发,保证偶数长度时 slow 落在前段末尾
ListNode *slow = head, *fast = head->next;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
ListNode* second = slow->next;
slow->next = nullptr; // 必须断链,否则两段互相牵连
return merge(sortList(head), sortList(second));
}
private:
static ListNode* merge(ListNode* a, ListNode* b) {
ListNode dummy(0);
ListNode* t = &dummy;
while (a && b) {
if (a->val <= b->val) {
t->next = a;
a = a->next;
} else {
t->next = b;
b = b->next;
}
t = t->next;
}
t->next = a ? a : b;
return dummy.next;
}
};
}
单元测试
以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。
lc0148::Solution s;
ListNode* a = buildList({4, 2, 1, 3});
CHECK_EQ(listToVec(s.sortList(a)), vector<int>{1, 2, 3, 4});
ListNode* b = buildList({-1, 5, 3, 4, 0});
CHECK_EQ(listToVec(s.sortList(b)), vector<int>{-1, 0, 3, 4, 5});
CHECK_TRUE(s.sortList(nullptr) == nullptr);
ListNode* c = buildList({1, 1, 1}); // 全相等,考验归并的稳定性
CHECK_EQ(listToVec(s.sortList(c)), vector<int>{1, 1, 1});