题解 | #单链表的排序#

归并排序。
在sortInList中把链表从中间分成两份

# 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
        def merge(left, right):
            prev = ListNode(0)
            temp = prev
            while left or right:
                if left and right:
                    if left.val < right.val:
                        temp.next = left
                        temp = temp.next
                        left = left.next
                    else:
                        temp.next = right
                        temp = temp.next
                        right = right.next
                elif left:
                    temp.next = left
                    break
                elif right:
                    temp.next = right
                    break
            return prev.next
        def findMid(left):
            if not left:
                return
            sleftw, fast = left, left.next
            while fast and fast.next:            
                sleftw = sleftw.next
                fast = fast.next.next
            return sleftw
        if not head or not head.next:
            return head
        prev = ListNode(0)
        prev.next = head    
        mid = findMid(head)
        newList = mid.next
        mid.next = None
        left = self.sortInList(head)
        right = self.sortInList(newList)
        res = merge(left, right)
        return res