单链表的排序【刷题记录】

一、题目描述

给定一个无序单链表，实现单链表的排序(按升序排序)。

示例1
输入：[1,3,2,4,5]
返回值：{1,2,3,4,5}

二、解题思路

(一) 辅助数组

主要通过辅助数组实现链表的排序
1、遍历链表并将链表结点存储到数组 tmp 中
2、通过对 tmp 进行排序，实现链表结点的排序
3、构建新链表结点 result，遍历数组 tmp ，拼接新的返回链表
图解：

class Solution:
    def sortInList(self , head ):
        # write code here
        if head == None or head.next == None:
            return head
        tmp = []
        tmp.append(head.val)
        # 遍历链表存储到数组中
        while head.next:
            head = head.next
            tmp.append(head.val)
        # 数组排序
        tmp.sort()
        # 重新构造新链表结点
        result = ListNode(-1)
        temp = result
        # 遍历数组，将数组中元素添加到新的链表中
        for i in tmp:
            tt = ListNode(i)
            temp.next = tt
            temp = temp.next
        return result.next

复杂度分析
时间复杂度O(NlogN)：N表示链表结点数量，遍历链表O(N)，数组排序(NlogN)，遍历数组O(N)
空间复杂度O(N)：使用额外数组占用空间O(N)

(二) 归并排序（递归）
首先使用快慢指针，把链表切割成两部分
然后在递归调用将单链表切分成单个单个的结点
最后好戏上场，逐个的去拼接left 和 right 递归回来的链表，按照从小到大从左到右的顺序把链表拼接上去

主要通过递归实现链表归并排序，有以下两个环节：
1、分割 cut 环节：找到当前链表中点，并从中点将链表断开（以便在下次递归 cut时，链表片段拥有正确边界）；
1）使用 fast,slow 快慢双指针法，奇数个节点找到中点，偶数个节点找到中心左边的节点。
2）找到中点 slow 后，执行 slow.next = None 将链表切断。
3）递归分割时，输入当前链表左端点 head 和中心节点 slow 的下一个节点 tmp(因为链表是从 slow 切断的)。
cut 递归终止条件：当head.next == None时，说明只有一个节点了，直接返回此节点
2、合并 merge 环节：将两个排序链表合并，转化为一个排序链表。
1）双指针法合并，建立辅助ListNode h 作为头部。
2）设置两指针 left, right 分别指向两链表头部，比较两指针处节点值大小，由小到大加入合并链表头部，指针交替前进，直至添加完两个链表。
3）返回辅助ListNode h 作为头部的下个节点 h.next。
时间复杂度 O(l + r)，l, r 分别代表两个链表长度。
3、特殊情况，当题目输入的 head == None 时，直接返回None。
图解：

class Solution:
    def sortInList(self , head ):
        # write code here
        if head == None or head.next == None:
            return head
        # cut is used to cut down list
        cut = head
        # use 
        slow = head
        fast = head
        # find mid node
        while fast and fast.next:
            cut = slow
            slow = slow.next
            fast = fast.next.next
        left = head
        right = cut.next
        cut.next = None
        left = self.sortInList(left)
        right = self.sortInList(right)
        return self.merge(left, right)
         
    def merge(self, left, right):
        guard = ListNode(0)
        p = guard
        while left and right:
            if left.val < right.val:
                guard.next = left
                left = left.next
            else:
                guard.next = right
                right = right.next
            # whatever append from left&nbs***bsp;right list must move guard point
            guard = guard.next
        # append remain list
        if left:
            guard.next = left
        if right:
            guard.next = right
        return p.next