题解 | #单链表的排序# #归并排序最优解#

#coding:utf-8
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 ):
        if head is None or head.next is 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