148. sort list

class (object):
    def sortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head:
            return head
        ans = mergeSort(head)
        return ans

def mergeSort(node):
    if not node or not node.next:
        return node
    slow,fast = node,node.next
    while fast and fast.next:
        fast = fast.next.next
        slow = slow.next
    left = node
    right = slow.next
    slow.next = None
    new_l = mergeSort(left)
    new_r = mergeSort(right)
    return merge(new_l,new_r)

def merge(l,r):
    head = ListNode(0)
    cur = head
    while l and r:
        if l.val<r.val:
            cur.next = l
            l = l.next
        else:
            cur.next = r
            r = r.next
        cur = cur.next
        cur.next = None
    if l:
        cur.next = l
    if r:
        cur.next = r
    return head.next