题目
Given the head of a linked list, return the list after sorting it in ascending order.
Follow up: Can you sort the linked list in O(n logn) time and O(1) memory (i.e. constant space)?
解题思路
使用归并排序的方法，使用快慢指针将链表拆成两个，分别排序，再合并
代码
class Solution:
def merge(self, h1, h2):
dummy = tail = ListNode()
while h1 and h2:
if h1.val < h2.val:
tail.next, tail, h1 = h1, h1, h1.next
else:
tail.next, tail, h2 = h2, h2, h2.next
tail.next = h1 or h2
return dummy.next
def sortList(self, head: ListNode) -> ListNode:
if not head or not head.next:
return head
pre, slow, fast = None, head, head
while fast and fast.next:
pre, slow, fast = slow, slow.next, fast.next.next
pre.next = None
return self.merge(self.sortList(head), self.sortList(slow))
