题解 | #单链表的排序#的Python解法

1. 解题思路

看到这题的第一反应就是利用数组的sort函数来自动排序然后更新链表中的节点值，这个思路很简单，就不画图解说，直接上代码。

2. 核心代码

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
# 
# @param head ListNode类 the head node
# @return ListNode类
class Solution:
    def sortInList(self , head):
        # write code here
        #获取头部节点
        h = head
        #创建一个排序数组
        l = []
        #当节点存在的时候，依次添加节点值到数组
        while h:
            l.append(h.val)
            h = h.next
        l.sort()       #利用sort函数对数组进行升序排列
        #创建新链表
        h = head
        i = 0      #索引从0开始
        #把排完序的数组重新赋值给新的链表，此时的链表的所有节点都是按升序排列的
        while h:
            h.val = l[i]
            h = h.next
            i += 1
        return head

3. 复杂度分析

时间复杂度： $O(nlogn)$ (n为链表的长度，数组排序的时间复杂度为 $O(nlogn)$ )
空间复杂度： $O(n)$ (新建的排序数组大小与链表长度n有关)

----------------------------------------------我是有点复杂的解法二分割线----------------------------------------------

4. 解法二

4.1 思路：归并排序（递归法）

此题另一种解法就是利用分治思想中比较经典的归并排序（Merge Sort）算法。
PS : 简单解释一下归并排序的含义👉：
把数组从中间开始切割成前后两部分，然后分别对前后两部分排序；再把排好序的两部分合并，此时的数组就是我们要找的有序数组。
具体到本题的思路：

找到切割链表的中间点，把链表分成左右两部分；然后通过递归找的终止条件（即只有一个节点的时候）；
接下来分别对左右两边的链表进行排序，然后合并排好序的链表。

这里结合示例1进行图解：
图片说明

4.2 核心代码

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
# 
# @param head ListNode类 the head node
# @return ListNode类
class Solution:
    def sortInList(self , head):
        # write code here
        #首先链表只有一个节点或没有节点的情况
        if not head or not head.next:
            return head
        #创建快慢两种指针
        slow, fast = head, head
        #去找中间位置来切断链表
        while fast.next and fast.next.next:
            slow, fast = slow.next, fast.next.next
        mid = slow.next
        slow.next = None                                           #找到左右两部分
        left, right = self.sortInList(head), self.sortInList(mid) #一直递归下去，直到左右两部分的节点都被切割开
        #分别对左右两边进行排序（升序）并合并
        res = ListNode(0)
        tail = res
        while left and right:
            if left.val < right.val:                             #如果左边节点的值时小于右边的时候
                tail.next, left = left, left.next                #那么tail将会在左边进行排序；否则在右边
            else:
                tail.next, right = right, right.next
            tail = tail.next
        #仅有左边或右边的情况
        if left:
            tail.next = left
        if right:
            tail.next = right
        return res.next

4.3 复杂度分析

时间复杂度： $O(nlogn)$ (n为链表的长度，分解链表的时间为log n，合并两个有序链表的时间为n)
空间复杂度： $O(logn)$ (n 为链表的长度，空间复杂度主要取决于递归调用的栈空间)