Sort a linked list in O(n log n) time using constant space complexity.
Example 1:
Input: 4->2->1->3 Output: 1->2->3->4
Example 2:
Input: -1->5->3->4->0 Output: -1->0->3->4->5
这个题目有好几种做法，因为包含O(n*lg(n)) 的主要排序方法有三种， merger sort， quick sort， heap sort。
1. Merge sort
实际上是利用了分治的思想，找中点，然后两边分别排序，最后将它们merge起来即可。
找中点的程序可以参考[LeetCode] 876. Middle of the Linked List_Easy tag: Linked List。
merge left， right的程序可以参考[LeetCode] 21. Merge Two Sorted Lists_Easy tag: Linked List。
code
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def findMiddle(self, head): if not head: return head slow, fast = head, head while fast: if fast.next is None or fast.next.next is None: return slow slow = slow.next fast = fast.next.next return slow def merge(self, l1, l2): dummy = ListNode(0) head = dummy while l1 and l2: if l1.val <= l2.val: head.next = l1 l1 = l1.next else: head.next = l2 l2 = l2.next head = head.next head.next = l1 if l1 else l2 return dummy.next def sortList(self, head: ListNode) -> ListNode: # merge sort . T: O(n * lg(n)) if head is None or head.next is None: return head middle = self.findMiddle(head) right = self.sortList(middle.next) middle.next = None left = self.sortList(head) return self.merge(left, right)
[LeetCode] 148. Sort List_Middle tag: Linked List
原文：https://www.cnblogs.com/Johnsonxiong/p/10801852.html