148. 排序鏈表
在 O(n log n) 時間復(fù)雜度和常數(shù)級空間復(fù)雜度下，對鏈表進(jìn)行排序。
示例:
輸入: 4->2->1->3
輸出: 1->2->3->4

解法1

采用歸并排序, 先找到鏈表的中間的一分為二, 左右兩個鏈表分別歸并排序, 再將排好序的鏈表合并.

class Solution(object):
    def sortList(self, head):
        if head == None or head.next == None:
            return head
        
        half = self.halfList(head)
        li, ri = head, half.next
        half.next = None
        
        li = self.sortList(li)
        ri = self.sortList(ri)
        
        pre = ListNode(-1)
        tail = pre
        while li != None and ri != None:
            if li.val < ri.val:
                tail.next = li
                li = li.next
            else:
                tail.next = ri
                ri = ri.next
        
            tail = tail.next
        if li != None:
            tail.next = li
        else:
            tail.next = ri
        return pre.next
        
    def halfList(self, head):
        if head == None or head.next == None:
            return head
        fast = head
        slow = head
        while fast.next != None and fast.next.next != None:
            slow, fast = slow.next, fast.next.next
        return slow

解法2

也是采用歸并排序, 運(yùn)用遞歸的思想和一個合并兩個鏈表的方法.

class Solution(object):
    def sortList(self, head):
        if head is None or head.next is None:
            return head
        mid = self.get_mid(head)
        l = head
        r = mid.next
        mid.next = None
        return self.merge(self.sortList(l), self.sortList(r))
    
    def merge(self, p, q):
            tmp = ListNode(0)
            h = tmp
            while p and q:
                if p.val < q.val:
                    h.next = p
                    p = p.next
                else:
                    h.next = q
                    q = q.next
                h = h.next
            if p:
                h.next = p
            if q:
                h.next = q
            return tmp.next
        
    def get_mid(self, node):
            if node is None:
                return node
            fast = slow = node
            while fast.next and fast.next.next:
                slow = slow.next
                fast = fast.next.next
            return slow