148. 排序链表

在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

示例：

输入1：

-1->5->3->4->0

输出1：

-1->0->3->4->5

解答：

def sortList(self,l):
    if not (l and l.next) : return l
    pre,fast,slow = None,l,l
    while (fast and fast.next):
        pre,fast,slow = slow,fast.next.next,slow.next
    pre.next = None
    return self.merge2SortedLists(*map(self.sortList,(l,slow)))
def merge2SortedLists(self,l1,l2):
    if l1 is None: return l2
    if l2 is None: return l1
    if l1.val >= l2.val: l1,l2 = l2,l1
    l1.next = self.merge2SortedLists(l1.next,l2)
    return l1 or l2