要求用时间复杂度O(nlgn)与空间复杂度O(1)来排序一个链表
2. 解决思路用快慢指针和归并排序来解决，思路见下图
class Solution:
def merge(self, left, right):
dummy_head = tail = ListNode(None)
while left and right:
if left.val <= right.val:
tail.next = left
left = left.next
else:
tail.next = right
right = right.next
tail = tail.next
if left and right is None:
tail.next = left
elif right and left is None:
tail.next = right
return dummy_head.next
def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if head is None or head.next is None:
return head
pre = None
slow = head
fast = head
while fast and fast.next:
pre = slow
slow = slow.next
fast = fast.next.next
pre.next = None
return self.merge(*map(self.sortList, (head, slow)))
