[leetcode sort]148. Sort List

Sort a linked list in O(n log n) time using constant space complexity.

以时间复杂度O(n log n)排序一个链表。

归并排序，在链表中不需要多余的主存空间

tricks:用快慢指针找到中间位置，划分链表

 1 class Solution(object):
 2     def sortList(self, head):
 3         if not head or not head.next:
 4             return head
 5         pre, slow, fast = None, head, head
 6         while fast and fast.next:
 7             pre, slow, fast = slow, slow.next, fast.next.next
 8         pre.next = None
 9         return self.merge(*(map(self.sortList,(head,slow))))
10     def merge(self,h1,h2):
11         dummy = tail = ListNode(None)
12         while h1 and h2:
13             if h1.val < h2.val:
14                 tail.next,h1, tail = h1,h1.next,h1
15             else:
16                 tail.next,h2,tail = h2,h2.next,h2
17             tail.next = h1 or h2
18         return dummy.next