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

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

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

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

 class Solution(object):
def sortList(self, head):
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(*(map(self.sortList,(head,slow))))
def merge(self,h1,h2):
dummy = tail = ListNode(None)
while h1 and h2:
if h1.val < h2.val:
tail.next,h1, tail = h1,h1.next,h1
else:
tail.next,h2,tail = h2,h2.next,h2
tail.next = h1 or h2
return dummy.next
05-11 19:57
查看更多