HHot 100C++ 图解

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) 空间(面试官常追问)。

快排在链表上最坏会退化,堆排序不方便,所以这题的标准答案是归并。

图解

-1 i0 5 i1 3 i2 4 i3 0 i4
链表结构(来自本仓库测试数据)

C++17 题解

src/07_linked_list.cpp35 行
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;
  }
};
}

单元测试

以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。

TEST q148_sort_list8 行
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});

↑↓ 选择↵ 打开/ 随时唤起