Leetcode148.排序链表（快速排序、自底向上归并排序）

题目描述：

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

示例：

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

快速排序方法：（空间复杂度为调用栈的深度：logn）

# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def sortList(self, head):
        bla, _ = self.sort(head)
        return bla
    
    def sort(self, head):
        if not head or not head.next:
        """若head为None，则返回None, None；若为单节点，则返回该节点"""
            return head, head

        partition_head = partition = node = head
        left_head = left_node = ListNode(0)
        right_head = right_node = ListNode(0)
        
        while node.next:
            node = node.next
            if node.val < partition.val:
                left_node.next = node
                left_node = node
            elif node.val > partition.val:
                right_node.next = node
                right_node = node
            else:
                partition.next = node
                partition = node
        
        left_node.next = right_node.next = partition.next = None

        left_head, left_tail = self.sort(left_head.next)
        right_head, right_tail = self.sort(right_head.next)

        if not left_tail:
            left_head = partition_head
        else:
            left_tail.next = partition_head

        partition.next = right_head

        if not right_tail:
            right_tail = partition
        return left_head, right_tail

自底向上归并排序：（空间复杂度为O(1)）

# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution(object):
    def sortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if head is None: return None

        def getSize(head):
            counter = 0
            while (head is not None):
                counter += 1
                head = head.next
            return counter

        def split(head, step):
            i = 1
            while (i < step and head):
                head = head.next
                i += 1

            if head is None: return None
            # disconnect
            temp, head.next = head.next, None
            return temp

        def merge(l, r, head):
            cur = head
            while (l and r):
                if l.val < r.val:
                    cur.next, l = l, l.next
                else:
                    cur.next, r = r, r.next
                cur = cur.next

            cur.next = l if l is not None else r
            while cur.next is not None: cur = cur.next
            return cur

        size = getSize(head)
        bs = 1
        dummy = ListNode(0)
        dummy.next = head
        l, r, tail = None, None, None
        while (bs < size):
            cur = dummy.next
            tail = dummy
            while cur:
                l = cur
                r = split(l, bs)
                cur = split(r, bs)
                tail = merge(l, r, tail)
            bs <<= 1
        return dummy.next