16-148. Sort List

题目描述：

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

Example 1:

Input: 4->2->1->3
Output: 1->2->3->4

Example 2:

Input: -1->5->3->4->0
Output: -1->0->3->4->5

代码：

 1 # Definition for singly-linked list.
 2 # class ListNode(object):
 3 #     def __init__(self, x):
 4 #         self.val = x
 5 #         self.next = None
 6 
 7 class Solution(object):
 8     def sortList(self, head):
 9         """
10         :type head: ListNode
11         :rtype: ListNode
12         """
13         if not head or not head.next:
14             return head
15     
16         pre, slow, fast = None, head, head
17         while fast and fast.next:
18             pre, slow, fast = slow, slow.next, fast.next.next
19         pre.next = None
20 
21         return self.merge(*map(self.sortList, (head, slow)))
22         
23     def merge(self, h1, h2):
24         dummy = tail = ListNode(None)
25         while h1 and h2:
26             if h1.val < h2.val:
27                 tail.next, tail, h1 = h1, h1, h1.next
28             else:
29                 tail.next, tail, h2 = h2, h2, h2.next
30     
31         tail.next = h1 or h2
32         return dummy.next