归并排序 python 安排

1. 首先使用快慢指针，把链表切割成两部分
2. 然后在递归调用将单链表切分成单个单个的结点
3. 最后好戏上场，逐个的去拼接left 和 right 递归回来的 链表，按照从小到大 从左到右的 顺序把 链表 拼接上去

class Solution:
    def sortInList(self , head ):
        if head is None&nbs***bsp;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