边工作边刷题：70天一遍leetcode: day 7

Sort List

要点：merge sort，recursion function不需要head和tail头尾指针来限定范围，直接把前后子list断开。用fast.next作为2指针条件，这样最后落在偏左边的结点，也就是后一个list的前一个元素

# 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
        """
        def sorthelper(head):
            if not head or not head.next: return head
            slow=fast=head
            while fast.next:
                fast=fast.next
                if fast.next:
                    slow=slow.next
                    fast=fast.next
        
            next = slow.next
            slow.next = None
            a = sorthelper(head)
            b = sorthelper(next)
            
            dummy = ListNode(0)
            cur = dummy
            while a and b:
                if a.val<b.val:
                    cur.next = a
                    a = a.next
                else:
                    cur.next = b
                    b = b.next
                cur = cur.next
                
            if a:
                cur.next = a
            elif b:
                cur.next = b
            return dummy.next
        
        return sorthelper(head)