Leetcode-148.排序链表

未分类
2.2k 词

注意归并排序的细节：
用快慢指针找到中间的指针。
中间指针在慢指针后面
注意慢指针要断链

image.png

快慢指针原理：

1
2
3
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next

退出时有两种可能：

  1. 链表长度是偶数

    • fast 先跑到最后一个节点，再走两步直接变成 None

    • 循环条件里 fast 为 None，退出

  2. 链表长度是奇数

    • fast 最后落在最后一个节点

    • fast.next 是 None，循环条件里 fast.next 为 None，退出

举例验证

  • 长度 4：1→2→3→4

    • 最后一步 fast=4，fast.next=None → 再走两步时 fast=None → 循环退出

  • 长度 5：1→2→3→4→5

    • 最后一步 fast=5，fast.next=None → 循环退出

快慢指针分割链表

1
2
mid = slow.next
slow.next = None

也就是说，mid 取的是 slow 的下一个节点。

快慢指针找中点的逻辑

  • slow 每次走一步

  • fast 每次走两步

  • 循环条件：while fast and fast.next:

循环退出时，slow 会落在 中点偏左的位置。

为什么不是直接 mid = slow

  • 如果直接取 mid = slow，那么递归时左半部分和右半部分会有 交叉节点。

  • 因为 slow 还连着后半部分链表，递归时左半部分就不纯粹了。

所以必须 断链：

1
2
mid = slow.next
slow.next = None   # 把 slow 和 mid 之间切断

这样得到：

  • 左半部分：从 head 到 slow

  • 右半部分：从 mid 到末尾

举例说明

链表：1 → 2 → 3 → 4

  • 初始：slow=1, fast=2

  • 迭代1：slow=2, fast=4

  • 退出时：slow=2

这时：

  • mid = slow.next = 3

  • 断链：slow.next = None

结果：

  • 左半部分：1 → 2

  • 右半部分：3 → 4

如果错误地用 mid = slow：

  • 左半部分：1 → 2 → …（还会连到 3）

  • 右半部分：2 → 3 → 4（和左半部分重叠）

递归就会出问题，甚至死循环。

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
# Definition for singly-linked list.

# class ListNode:

#     def __init__(self, val=0, next=None):

#         self.val = val

#         self.next = next

class Solution:

    def merge(self,L1,L2):

        dummy=ListNode(0)

        tail=dummy

        while L1  and L2 :

            if L1.val > L2.val:

                tail.next=L2

                L2=L2.next

            else:

                tail.next=L1

                L1=L1.next

            tail=tail.next

        while L1:

            tail.next=L1

            L1=L1.next

            tail=tail.next

        while L2:

            tail.next=L2

            L2=L2.next

            tail=tail.next

        return dummy.next

    def merge_sort(self,head):

        if  not head or not head.next:

            return head

        slow,fast=head,head.next

        while fast and fast.next :

            slow=slow.next

            fast=fast.next.next

        mid=slow.next

        slow.next=None

        left=self.merge_sort(head)

        right=self.merge_sort(mid)

        return self.merge(left,right)

    def sortList(self, head):

        return self.merge_sort(head)

排序链表 vs 数组归并排序 的对比总结：

数组 vs 链表归并排序对比

1. 如何分割

  • 数组

    • 通过下标 mid = (left+right)//2 来划分区间 [left, mid] 和 [mid+1, right]。

    • 不需要真正切断数组，递归时用下标控制。

  • 链表

    • 不能随机访问，只能用 快慢指针 找到中点。

    • 找到 slow 后，通过 slow.next = None 来 断链，分成两段独立子链表。

2. 如何合并

  • 数组

    • 在 merge(arr, left, mid, right) 时，需要复制左右两段到临时数组 L、R，再一个个写回原数组。

    • 时间 O(n)，额外空间 O(n)。

  • 链表

    • 用 merge(l1, l2) 直接操作指针，把两个有序链表拼接起来。

    • 不需要额外数组空间，只需要几个辅助指针。

    • 时间 O(n)，空间 O(1)。

3. 递归终止条件

  • 数组

    1
    if left >= right: return

    只剩一个元素（或空区间）时，直接返回。

  • 链表

    1
    if not head or not head.next: return head

    空链表或单节点链表，天然有序，直接返回。

4. 时间复杂度

  • 两者都是：

    • 递归分治深度 O(log n)

    • 每层合并 O(n)

    • 总复杂度 O(n log n)

5. 空间复杂度

  • 数组归并排序

    • 需要额外临时数组（每次 merge 时），总体 O(n) 辅助空间。

  • 链表归并排序

    • 只需要少量指针变量，辅助空间 O(1)（如果不算递归栈）。

    • 这是链表排序的一个优势。