148. 排序链表 [medium]

148. 排序链表 [medium]

https://leetcode-cn.com/problems/sort-list/

在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

示例 1:

输入: 4->2->1->3
输出: 1->2->3->4

示例 2:

输入: -1->5->3->4->0
输出: -1->0->3->4->5

通过次数71,933 | 提交次数109,039

Third Try

2020-07-10

优化的快排递归版本

针对有许多相等的元素的情况，对快排进行三段排序，小于，大于和等于pivot节点，然后递归处理小于和大于的情况。

本来最差情况是O(N^2),最优情况是O(NlgN),现在最差情况依然是O(N^2),但是最优情况可以到O(N)了，也因此能够通过测试集。 当然由于递归的存在，依然是O(lgN)的空间复杂度，而不是O(1).

有了前面归并排序的基础，快排的写起来快了不少，但快排的非递归版本真是写不动了，在非递归归并排序那里累坏了。

• 快排的补充笔记：

先选取一个pivot点（任意点都行，一般选择中间点，或者第一个点），然后把比pivot小的分一遍，比pivot大的分一边，与pivot相等的分一遍。然后在分别对pivot的左右两侧进行递归处理，一直到只剩下一个。因此在函数中，看起来是先进行初略排序，然后再分别对两侧进行递归。

fast sort的写法与merge sort是相反的，merge sort是先对半到底，然后再排序。

# 优化的递归版本
class Solution(object):
    def sortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        # 还得来个快排版本
        # 随便选个开头作为中间点，然后分开左右
        # 最差情况是O(N^2)，随机情况下是O(NlgN)
        # 跟merge sort不同的地方在于先初略排序，然后再对半递归
        # merge sort则是先对半递归，然后再排序，是稳定的O(NlgN)
        # print("received", head)
        # 修改超时版本，提供一个中间相等的middle list，加速一下
        if not(head and head.next):
            return head 
        pick = node = head
        left = leftend = ListNode(None) 
        right = rightend = ListNode(None)
        while node.next:
            nnode = node.next 
            if nnode.val > pick.val:
                rightend.next = nnode 
                rightend = rightend.next 
                node.next = nnode.next # 跳过, 位置也要在一个操作之前
                nnode.next = None # 断开才行，只要一点
            elif nnode.val < pick.val:
                leftend.next = nnode 
                leftend = leftend.next 
                node.next = nnode.next 
                nnode.next = None 
            elif node.val == pick.val:
                node = nnode

        middle_end = node 
        # print("pick", pick.val)
        # print("left", pick.next)
        # print('right', right.next)
        left_part = self.sortList(left.next)
        right_part = self.sortList(right.next)
        middle_end.next = right_part
        if not left_part:  # 左侧可能啥都没有，右侧则不用管
            return pick
        mark_left = left_part
        while mark_left.next:  # 寻找左侧的末尾，然后再添加middle点
            mark_left = mark_left.next 
        mark_left.next = pick 
        return left_part
                

• 执行用时：124 ms, 在所有 Python 提交中击败了89.40%的用户
• 内存消耗：28 MB, 在所有 Python 提交中击败了9.09%的用户

超时的快排递归版本

普通的快排递归写法。本来常见的快排是选取中间节点当哨兵的，但链表里这么搞太麻烦了，直接选第一个当哨兵在速度上也没有不同。然后就是筛选比哨兵小的元素，筛选比哨兵大的元素，各自进行递归快排，再按顺序一起拼接起来就行。

最差情况是O(N^2),最优情况是O(NlgN)，通过了不少测试案例，但在遇到很多相等元素测试集的时候，还是超时挂掉了。

class Solution(object):
    def sortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        # 还得来个快排版本
        # 随便选个开头作为中间点，然后分开左右
        # 最差情况是O(N^2)，随机情况下是O(NlgN)
        # 跟merge sort不同的地方在于先初略排序，然后再对半递归
        # merge sort则是先对半递归，然后再排序，是稳定的O(NlgN)
        # print("received", head)
        if not(head and head.next):
            return head 
        pick = node = head 
        right = rightend = ListNode(None)
        while node.next:
            nnode = node.next 
            if nnode.val > pick.val:
                rightend.next = nnode 
                rightend = rightend.next 
                node.next = nnode.next # 跳过, 位置也要在一个操作之前
                nnode.next = None # 断开才行，只要一点
            else:
                node = nnode
        # print("pick", pick.val)
        # print("left", pick.next)
        # print('right', right.next)
        left_part = self.sortList(pick.next)
        right_part = self.sortList(right.next)
        pick.next = right_part
        if not left_part:  # 左侧可能啥都没有，右侧则不用管
            return pick
        mark_left = left_part
        while mark_left.next:  # 寻找左侧的末尾，然后再添加middle点
            mark_left = mark_left.next 
        mark_left.next = pick 
        return left_part
                

Second Try

2020-07-10

耗费太多时间了，知道了mergeSort递归解法后其实理解非递归解法没有问题，但是边界要考虑的条件实在太多了，各种写各种bug，最后才调试出一个通过版本。。。

耗费时间实在太长了，在一些简单的边界条件判断上有时候还要通过测试才能确定，对边界的思考还不够清晰啊。

据说还有用快排的，待会再考虑写个快排版本吧，顺便复习下快排。

注意的bug:

• 不能用找中间点的方法，比如2，3，4，5，1在round为8的时候，应该在5的部分切开，找中间点反而在4的地方切开
• 对group间隔进行判断终结的时候，要确保上一个进行间隔的一半已经覆盖了整个链表

class Solution(object):
    def sortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """

        # 不能用找中间点的方法，比如2，3，4，5，1在round为8的时候，应该在5的部分切开，找中间点反而在4的地方切开

        # 来个自底向上的merge sort写法
        dummy = node = ListNode(None)
        dummy.next = head 
        xlen = 0
        while node.next:
            xlen += 1
            node = node.next 
            
        group = 1 
        while group // 2 <= xlen:
            group *= 2
            lead_node = dummy
            # print("group", group, dummy)
            while lead_node.next:
                # print("next part", lead_node)

                # 找出左边的部分和右边的部分，然后再考虑下前后的状态标记，就变成了这么复杂琐碎的写法了
                # 如果用函数cut(linklist, pre_n)应该会优化许多
                cleft = cright = group // 2
                markn = lead_node
                left = lead_node.next  
                while cleft > 1 and left.next:    
                    left = left.next 
                    cleft -= 1                    
                right = left.next
                if not right: # 如果只有左侧，免排进入下一轮
                    break
                # 继续找右侧的完整链路
                while cright > 1 and right.next:
                    right = right.next 
                    cright -= 1 
                # 一堆边界条件，考虑前后链接的完整性之类
                next_part = right.next 
                right.next = None 
                right = left.next 
                left.next = None 
                left = lead_node.next 

                while left and right:
                    if left.val <= right.val:
                        markn.next = left
                        left = left.next 
                    else:
                        markn.next = right 
                        right = right.next 
                    markn = markn.next  
                    markn.next = None 
                markn.next = left or right
                while markn.next: # 不写成while，又是一个bug
                    markn = markn.next # 没有补又是一个bug
                # print('after sort', dummy)
                # 补全之前被切断的部分
                lead_node = markn 
                # print("markn", markn)
                # print("next part", next_part)
                markn.next = next_part
                # print("wtf", dummy)
            
        return dummy.next                 

• 执行用时：244 ms, 在所有 Python 提交中击败了29.42%的用户
• 内存消耗：27.9 MB, 在所有 Python 提交中击败了9.09%

• bug version

不能用找中间点的方法进行切分，比如2，3，4，5，1在round为8的时候，应该在5的部分切开，找中间点反而在4的地方切开。

class Solution(object):
    def sortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """

        # 不能用找中间点的方法，比如2，3，4，5，1在round为8的时候，应该在5的部分切开，找中间点反而在4的地方切开
        # 这又是一个bug
        def find_middle(head):
            if not (head and head.next):
                return head 
            slow = head 
            fast = head.next 
            while fast and fast.next:
                slow = slow.next 
                fast = fast.next.next 
            return slow 

        # 来个自底向上的merge sort写法
        dummy = ListNode(None)
        dummy.next = node = head 
        xlen = 0
        while node.next:
            xlen += 1
            node = node.next 
        group = 1 
        while group // 2 <= xlen:
            group *= 2
            lead_node = dummy
            print("group", group, dummy)
            while lead_node.next:
                print("next part", lead_node)
                c = group
                markn = lead_node
                start = lead_node.next  
                while c > 1 and start.next:    
                    start = start.next 
                    c -= 1            
                next_part = start.next 
                # print("next lead", next_lead)
                start.next = None # 先切开
                mid = find_middle(lead_node.next)
                # print("mid",mid.val)
                right = mid.next 
                mid.next = None
                left = lead_node.next
                print("left part", left)
                print('right part', right)
                print("lead part", markn)
                while left and right:
                    if left.val <= right.val:
                        markn.next = left
                        left = left.next 
                    else:
                        markn.next = right 
                        right = right.next 
                    markn = markn.next  
                    markn.next = None 
                markn.next = left or right
                while markn.next: # 不写成while，又是一个bug
                    markn = markn.next # 没有补又是一个bug
                print('after sort', dummy)
                # 补全之前被切断的部分
                lead_node = markn 
                # print("markn", markn)
                # print("next part", next_part)
                markn.next = next_part
                # print("wtf", dummy)
            
        return dummy.next                 

First Try

2020-07-09

复杂度为O(nlgn)那么就要求是merge sort一类的算法了，而常数级空间已经排除掉用list来讨巧的做法。

一开始是不知道怎么在链表里面用merge sort的算法，做了147的insertion sort终于有了点思路。merge sort前阵子才复习过，但并没有练手，所以一开始写个递归也是踌躇了许久，递归的思路还是挺反顺序直觉的，还好先按照递归成功后的状态处理来写递归问题，总算搞了出来，清晰了许多。

不过用了递归方法，空间就已经不再是常数级别了，这就尴尬了。难道还要从底部直接往上推导merge sort吗？

另外再补充下merge sort笔记：

merge sort归并排序的思路，就是先对半分，把两边通过递归处理排序好之后，再把两边按照顺序合并起来。因此处理思路首先就是拆分链表，通过递归处理左右链表，并假设已经处理成功，对返回的两个链表进行简单的比较合并，然后就自然搞定了。

因此merge sort不管什么前提条件都是O(NlgN)的复杂度。

对比快排则是相反的思路，先进行初略的比较切分为两端，再在两侧进行初略排序切分，不断递归下去。看起来跟merge sort其实差不多，区别是先排序，然后再递归。好的情况复杂度是O(NlgN), 差的条件下是O(N^2)，不过优化成三段排序后，好的情况可以是O(N).

class Solution(object):
    def sortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        # 来个练手merge排序

        def find_middle(head): # 每次还是需要对奇偶画个图才能确定slow代表哪边
            if not (head and head.next):
                return head 
            slow = head 
            fast = head.next 
            while fast and fast.next:
                slow = slow.next 
                fast = fast.next.next 
            return slow 
        
        def merge_sort(head):
            if head and head.next is None:  # head为None的情况不应该存在
                return head 
            middle = find_middle(head)
            right = middle.next 
            middle.next = None 
            left = merge_sort(head)
            right = merge_sort(right)
            dummy = node = ListNode(None)
            while left and right:
                if left.val <= right.val:
                    node.next = left 
                    node = node.next 
                    left = left.next
                else:
                    node.next = right 
                    node = node.next 
                    right = right.next 
            node.next = left or right 
            return dummy.next 
        
        if not head:
            return head 

        return merge_sort(head)

• 执行用时：192 ms, 在所有 Python 提交中击败了80.71%的用户
• 内存消耗：28.1 MB, 在所有 Python 提交中击败了9.09%的用户