leetcode148 Sort List

 1 """
 2 Sort a linked list in O(n log n) time using constant space complexity.
 3 Example 1:
 4 Input: 4->2->1->3
 5 Output: 1->2->3->4
 6 Example 2:
 7 Input: -1->5->3->4->0
 8 Output: -1->0->3->4->5
 9 """
10 """
11 这道题，主要分为两个步骤。
12 第一是用快慢指针法，找到链表的中间位置将链表一分为二
13 第二与leetcode21类似，https://www.cnblogs.com/yawenw/p/12273855.html
14 将两个链表合并为一个有序链表
15 整个过程采用递归的方法
16 """
17 
18 class ListNode:
19     def __init__(self, x):
20         self.val = x
21         self.next = None
22 
23 class Solution:
24     def sortList(self, head):
25         if not head or not head.next:
26             return head
27         cut, slow, fast = head, head, head  # cut指针用来截断链表
28         while fast and fast.next:
29             cut = slow
30             slow = slow.next
31             fast = fast.next.next
32         cut.next = None  # bug 没写.next 理解截断的作用
33         l1 = self.sortList(head)
34         l2 = self.sortList(slow)
35         return self.Merge(l1, l2)
36 
37     def Merge(self, l1, l2):
38         head = ListNode(0)
39         first = head  # 存结果的头指针
40         while l1 and l2:
41             if l1.val < l2.val:
42                 head.next = l1
43                 l1 = l1.next
44             else:
45                 head.next = l2
46                 l2 = l2.next
47             head = head.next  # !!!head随之向后移 容易忘
48         head.next = l1 if l1 else l2
49         # if not l2:
50         #     move.next = l1
51         # if not l1:
52         #     move.next = l2
53         return first.next