剑指 Offer II 077. 链表排序

题目描述

给定链表的头结点 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) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

链接：https://leetcode-cn.com/problems/7WHec2

解题思路

方法1.选择排序
复杂度为O(n^2)，只需要交换值就可以。
不过超时。
方法2.归并排序
复杂度为O(nlogn)。
通过递归实现链表归并排序，有以下两个环节：
分割 cut 环节：
1. 找到当前链表中点，并从中点将链表断开（以便在下次递归 cut 时，链表片段拥有正确边界）；
2. 我们使用 fast,slow 快慢双指针法，奇数个节点找到中点，偶数个节点找到中心左边的节点。
3. 找到中点 slow 后，执行 slow.next = None 将链表切断。
4. 递归分割时，输入当前链表左端点 head 和中心节点 slow 的下一个节点 tmp(因为链表是从 slow 切断的)。
5. cut 递归终止条件： 当head.next为None时，说明只有一个节点了，直接返回此节点。

合并 merge 环节： 将两个排序链表合并，转化为一个排序链表。
此处使用双指针法合并，建立辅助ListNode node 作为头部。
1. 设置两指针 left, right 分别指向两链表头部，比较两指针处节点值大小，由小到大加入合并链表头部，指针交替前进，直至添加完两个链表。
2. 返回辅助ListNode h 作为头部的下个节点 node.next。
3. 时间复杂度 O(l + r)，l, r 分别代表两个链表长度。

当题目输入的 head为None 时，直接返回None。

解题代码

方法1.选择排序（超时）

class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        if not head:
            return None
        cur, node = head, head
        while cur.next:
            node = cur.next
            while node:
                if node.val < cur.val:
                    node.val, cur.val = cur.val, node.val  # 保证cur为当前遍历过的链中最小的一个
                node = node.next
            cur = cur.next  # 此时cur已经为此次遍历中最小的
        return head

方法2.归并排序

class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        # head为None或者递归到单个时终止
        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
        # 针对左半部分和右半部分逐渐拆开排序
        left_start, right_start = head, slow.next
        slow.next = None
        # left和right为已经排序好的两半链表
        left, right = self.sortList(left_start), self.sortList(right_start)
        # 结果链表，注意这个链表的第一个node是空的
        node = result_head = ListNode(0)
        while left and right:
            if left.val < right.val:
                node.next = left
                left = left.next
            else:
                node.next = right
                right = right.next
            node = node.next
        node.next = left if not right else right
        return result_head.next

执行结果

执行结果：通过
执行用时：324 ms, 在所有 Python3 提交中击败了69.74%的用户
内存消耗：30.2 MB, 在所有 Python3 提交中击败了72.42%的用户