148. 排序链表

Posted on Edited on In Views: Word count in article: 731 Reading time ≈ 1 mins.

148. 排序链表

题目链接：148. 排序链表

题目描述

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

你可以在 $O(n \log n)$ 时间复杂度和常数级空间复杂度（不考虑递归栈的开销）下解决这个问题吗？

核心思考：链表归并排序 (Merge Sort)

要达到 $O(n \log n)$ 的时间复杂度，最经典且适合链表结构的算法是归并排序。

  1. 分割阶段（Divide）：
    • 使用**快慢指针（Fast & Slow Pointers）**来寻找链表的中间节点。
    • 关键操作：在找到中间节点后，必须将前一半链表的结尾指针（即 pre.next）置为空。这一步彻底将长链表单向解耦成两个互不相干的独立子链表。
    • 递归地对这两个子链表继续进行分割，直到链表长度为 0 或 1。
  2. 合并阶段（Conquer & Merge）：
    • 我们拥有两个已经局部有序的子链表 list1 和 list2。
    • 使用辅助节点 dummy 建立一个新链表，通过双指针比较大小，按从小到大的顺序将节点逐个挂载。
    • 最后将剩余未遍历完的子链表直接连接到新链表的末尾。

这种方法充分利用了链表“不需要物理连续存储”和“易于重新挂载”的特性，比快速排序等在链表上表现更稳定。

解题思路 (Python)

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
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 递归终止：链表为空或只有一个节点已然有序
        if head is None or head.next is None:
            return head
        
        # 1. 分割：利用快慢指针找到中点并切断
        head2 = self.mid_node(head)

        # 2. 递归：分别对左右两侧进行排序
        head = self.sortList(head)
        head2 = self.sortList(head2)

        # 3. 合并：将两个有序链表合并为一个
        return self.merge(head, head2)

    def mid_node(self, head):
        slow = fast = head
        pre = None
        while fast and fast.next:
            pre = slow
            slow = slow.next
            fast = fast.next.next
        
        # 核心：从中点切断，形成两个独立的列表
        if pre:
            pre.next = None
        return slow

    def merge(self, list1, list2):
        cur = dummy = ListNode()
        while list1 and list2:
            if list1.val < list2.val:
                cur.next = list1
                list1 = list1.next
            else:
                cur.next = list2
                list2 = list2.next
            cur = cur.next
        
        # 连接剩余部分
        cur.next = list1 if list1 else list2
        return dummy.next

复杂度分析

  • 时间复杂度：$O(N \log N)$，其中 $N$ 为链表的长度。归并排序的分割层数为 $\log N$，每一层合并的总工作量为 $N$。
  • 空间复杂度：$O(\log N)$。虽然合并过程不需要额外数组空间，但递归调用的系统栈深度取决于 $\log N$。
    说明：为了逻辑更安全，代码中为 mid_node 函数增加了对 pre 的空值校验。

ACM 模式

本节提供 ACM 竞赛风格的完整可运行代码，包含输入输出处理。

输入格式：

1
num1 num2 num3 ... numN

输入一行整数数组，以空格分隔。

完整代码：

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
import sys

class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
    # 递归终止：链表为空或只有一个节点已然有序
    if head is None or head.next is None:
        return head

    # 1. 分割：利用快慢指针找到中点并切断
    head2 = self.mid_node(head)

    # 2. 递归：分别对左右两侧进行排序
    head = self.sortList(head)
    head2 = self.sortList(head2)

    # 3. 合并：将两个有序链表合并为一个
    return self.merge(head, head2)

def main():
    nums = list(map(int, sys.stdin.read().strip().split()))

    sol = Solution()
    result = sol.sortList(nums)
    for v in result:\n        print(v, end=' ')\n    print()

if __name__ == "__main__":
    main()

运行示例：

1
echo "2 -1 3 4 -5" | python solution.py