Sort a linked list in O(n log n) time using constant space complexity.
(实现实现复杂度为O(nlog(n))的链表排序)
Example:
1. 归并排序
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47
|
class (object): def merge(self, left, right): new_head = ListNode(0) cur, left_i, right_i = new_head, left, right while left_i and right_i: if left_i.val < right_i.val: cur.next = left_i left_i = left_i.next else: cur.next = right_i right_i = right_i.next cur = cur.next if left_i: cur.next = left_i else: cur.next = right_i return new_head.next def sortList(self, head): """ :type head: ListNode :rtype: ListNode """ if not head or not head.next: return head slow, fast = head, head.next while fast and fast.next: slow = slow.next fast = fast.next.next middle = slow.next slow.next = None left = self.sortList(head) right = self.sortList(middle) return self.merge(left, right)
|
近期评论