【LeetCode 单链表专项】排序链表（148）

文章目录

• • 1. 题目
  • • 1.1 示例
    • 1.2 说明
    • 1.3 限制
    • 1.4 进阶
  • 2. 解法一（自顶向下归并排序）
  • • 2.1 分析
    • 2.2 解答
    • • 2.2.1 递归合并
      • 2.2.2 迭代合并
    • 2.3 复杂度
  • 3. 解法二（自底向上归并排序）
  • • 3.1 分析
    • 3.2 解答
    • 3.3 复杂度

1. 题目

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

1.1 示例

• 示例 $1$ ：
  • 输入： head = [4, 2, 1, 3]
  • 输出： [1, 2, 3, 4]

• 示例 $2$ ：
  • 输入： head = [-1, 5, 3, 4, 0]
  • 输出： [-1, 0, 3, 4, 5]

示例 $3$ ：

• 输入： head = []
• 输出： []

1.2 说明

• 来源： 力扣（LeetCode）
• 链接： https://leetcode-cn.com/problems/sort-list/

1.3 限制

• 链表中节点的数目在范围 $[0,5\ast 10^4]$ 内
• $-10^5<=\text{Node.val}<=10^5$

1.4 进阶

你可以在 $O(n\text{log}n)$ 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

2. 解法一（自顶向下归并排序）

2.1 分析

题目的进阶问题要求达到 $O(n\log n)$ 的时间复杂度，典型的拥有该时间复杂度的排序算法如下：

• 【常见算法Python描述】基于分治思想的归并排序简介与实现；
• 【常见算法Python描述】基于分治思想的快速排序简介与实现；
• 【常见算法Python描述】堆排序简介及实现。

在这三者中快速排序最坏的时间复杂度为 $O(n^2)$ ，堆排序又更适合对数组型序列进行排序，而最适合对链表进行排序的就是归并排序了。

选择好排序算法之后，接下来就是具体实现了。归并排序所基于的分治思想，其大概要点如下：

• 分：如果序列 $s$ 仅有 $0$ 个或 $1$ 个元素，因为序列已有序，则直接返回 $s$ 即可；否则（序列至少有 $2$ 个元素），将序列 $s$ 中所有元素移动至两个序列 $s_1$ 和 $s_2$ 中，每一个序列都大致包含 $s$ 中的一半元素，即 $s_1$ 中包含 $\lfloor n/2\rfloor$ 个元素， $s_2$ 中包含 $\lceil n/2\rceil$ 个元素；
• 治：对 $s_1$ 和 $s_2$ 进行递归排序；
• 合：将已排好序的 $s_1$ 和 $s_2$ 中的元素放回原序列 $s$ 中。

由上可知，正确使用归并排序主要需要解决两个问题：每次递归之前需要将链表分成元素数量大致相同的两个部分，在递归之后又需要将两个有序序列合并成一个新的有序序列，因此：

• 对于第一个问题，针对数组型的数据类型这很简单，因为可以直接得到总的元素个数，直接除以二然后就可以得到想要的结果，而对于链表而言，这意味着需要找到链表的中间节点。实际上，为了快速找到链表的中间节点，可以使用快慢指针的方式；
• 对于第二个问题，这在【LeetCode 单链表专项】合并两个有序链表（21）我们也已经给出了解答。

2.2 解答

2.2.1 递归合并

由【LeetCode 单链表专项】合并两个有序链表（21）可知，合并两个有序链表的过程既可以使用递归的方式，也可以使用迭代的方式，因此，下面两种实现只是在合并的过程中分别使用了递归和迭代的方式，其他二者并无差别。

from typing import Optional


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class LinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def append(self, val: int):
        node = ListNode(val)
        if self.head is None:
            self.head = node
            self.tail = node
        else:
            self.tail.next = node
            self.tail = self.tail.next


class Solution:
    def _find_middle(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        predecessor = slow = fast = head
        while fast and fast.next:
            predecessor = slow
            slow, fast = slow.next, fast.next.next
        predecessor.next = None
        return slow

    def _recursive_merge(self, lnk_lst1: Optional[ListNode], lnk_lst2: Optional[ListNode]) -> Optional[ListNode]:
        if not lnk_lst1:
            return lnk_lst2
        if not lnk_lst2:
            return lnk_lst1
        if lnk_lst1.val < lnk_lst2.val:
            head = lnk_lst1
            head.next = self._recursive_merge(lnk_lst1.next, lnk_lst2)
        else:
            head = lnk_lst2
            head.next = self._recursive_merge(lnk_lst1, lnk_lst2.next)
        return head

    def sort_list(self, head: ListNode) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        middle = self._find_middle(head)
        sorted_head = self.sort_list(head)
        sorted_middle = self.sort_list(middle)
        return self._recursive_merge(sorted_head, sorted_middle)


def main():
    values = [-1, 5, 3, 4, 0]
    lnk_lst = LinkedList()
    for val in values:
        lnk_lst.append(val)

    sln = Solution()
    head = sln.sort_list(lnk_lst.head)  # -1	0	3	4	5

    cursor = head
    while cursor:
        print(cursor.val, end='\t')
        cursor = cursor.next


if __name__ == '__main__':
    main()

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

2.2.2 迭代合并

from typing import Optional


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

        
class Solution:
    def _find_middle(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        predecessor = slow = fast = head
        while fast and fast.next:
            predecessor = slow
            slow, fast = slow.next, fast.next.next
        predecessor.next = None
        return slow

    def _iterative_merge(self, lnk_lst1: Optional[ListNode], lnk_lst2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0)
        cursor, cursor1, cursor2 = dummy, lnk_lst1, lnk_lst2
        while cursor1 and cursor2:
            if cursor1.val <= cursor2.val:
                cursor.next = cursor1
                cursor1 = cursor1.next
            else:
                cursor.next = cursor2
                cursor2 = cursor2.next
            cursor = cursor.next
        if cursor1:
            cursor.next = cursor1
        elif cursor2:
            cursor.next = cursor2
        return dummy.next

    def sort_list(self, head: ListNode) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        middle = self._find_middle(head)
        sorted_head = self.sort_list(head)
        sorted_middle = self.sort_list(middle)
        return self._iterative_merge(sorted_head, sorted_middle)

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

实际上，观察上述 sort_list 方法的内部调用，实际上和二叉树的后序遍历如出一辙。

2.3 复杂度

• 时间复杂度： $O(n\log n)$ ；
• 空间复杂度： $O(\log n)$ ，即取决于递归调用的最大深度。

3. 解法二（自底向上归并排序）

3.1 分析

• 作者： LeetCode-Solution

使用自底向上的方法实现归并排序，则可以达到 $O(1)$ 的空间复杂度，实际上下列解法和【常见算法Python描述】基于分治思想的归并排序简介与实现中给出的归并排序迭代实现的思想如出一辙，只是由于这里待排序列是链表，具体代码实现差别较大，这里是先求得链表的长度 length，然后将链表拆分成子链表进行合并。

具体做法如下：

• 使用 sub_length 表示每次需要排序的子链表的长度，初始时 sub_length = 1 。
• 每次将链表拆分成若干个长度为 sub_length 的子链表（最后一个子链表的长度可以小于 sub_length ），按照每两个子链表一组进行合并，合并后即可得到若干个长度为 sub_length * 2 的有序子链表（最后一个子链表的长度可以小于 sub_length * 2 ）。合并两个子链表仍然使用【LeetCode 单链表专项】合并两个有序链表（21）的做法。
• 将 sub_length 的值加倍，重复第 $2$ 步，对更长的有序子链表进行合并操作，直到有序子链表的长度大于或等于 length ，整个链表排序完毕。

如何保证每次合并之后得到的子链表都是有序的呢？可以通过数学归纳法证明。

• 初始时 sub_length = 1 ，每个长度为 $1$ 的子链表都是有序的；
• 如果每个长度为 sub_length 的子链表已经有序，合并两个长度为 sub_length 的有序子链表，得到长度为 sub_length * 2 的子链表，一定也是有序的；
• 当最后一个子链表的长度小于 sub_length 时，该子链表也是有序的，合并两个有序子链表之后得到的子链表一定也是有序的。

下图分别是当 sub_length 为 $1$ 、 $2$ 和 $4$ 的时候代码的执行过程：

• sub_length = 1 ：

• sub_length = 2 ：

• sub_length = 4 ：

3.2 解答

from typing import Optional


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class LinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def append(self, val: int):
        node = ListNode(val)
        if self.head is None:
            self.head = node
            self.tail = node
        else:
            self.tail.next = node
            self.tail = self.tail.next


class Solution:
    def _iterative_merge(self, lnk_lst1: Optional[ListNode], lnk_lst2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0)
        cursor, cursor1, cursor2 = dummy, lnk_lst1, lnk_lst2
        while cursor1 and cursor2:
            if cursor1.val <= cursor2.val:
                cursor.next = cursor1
                cursor1 = cursor1.next
            else:
                cursor.next = cursor2
                cursor2 = cursor2.next
            cursor = cursor.next
        if cursor1:
            cursor.next = cursor1
        elif cursor2:
            cursor.next = cursor2
        return dummy.next

    def sort_list(self, head: ListNode) -> Optional[ListNode]:
        length = 0
        node = head
        while node:
            length += 1
            node = node.next

        dummy = ListNode(0, head)
        sub_length = 1
        while sub_length < length:
            prev, curr = dummy, dummy.next
            while curr:
                head1 = curr
                for i in range(1, sub_length):
                    if curr.next:
                        curr = curr.next
                    else:
                        break
                head2 = curr.next
                curr.next = None
                curr = head2
                for i in range(1, sub_length):
                    if curr:
                        curr = curr.next
                    else:
                        break

                succ = None
                if curr:
                    succ = curr.next
                    curr.next = None

                merged = self._iterative_merge(head1, head2)
                prev.next = merged
                while prev.next:
                    prev = prev.next
                curr = succ
            sub_length <<= 1

        return dummy.next


def main():
    values = [-1, 5, 3, 4, 0]
    lnk_lst = LinkedList()
    for val in values:
        lnk_lst.append(val)

    sln = Solution()
    head = sln.top_down_sort_list(lnk_lst.head)  # -1	0	3	4	5

    cursor = head
    while cursor:
        print(cursor.val, end='\t')
        cursor = cursor.next


if __name__ == '__main__':
    main()

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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102

3.3 复杂度

• 时间复杂度： $O(n\log n)$ ；
• 空间复杂度： $O(1)$ 。