在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
这就需要分析一下各个排序算法的复杂度了。时间复杂度在O(nlogN)的排序算法是快速排序，堆排序，归并排序。但是快排的最坏时间复杂度是O(n^2),平均时间复杂度为O(nlogn)，所以不考虑快速排序。而堆排序太繁琐了。生硬地排除了。对于数组来说占用的空间复杂度为O(1),O(n),O(n)。但是对于链表来说使用归并排序占用空间为O(1).
所以，其实就是个归并排序题。
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def sortList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if head is None or head.next is None:
return head
mid = self.get_mid(head)
l = head
r = mid.next
mid.next = None
return self.merge(self.sortList(l), self.sortList(r))
def merge(self, p, q):
tmp = ListNode(0)
h = tmp
while p and q:
if p.val < q.val:
h.next = p
p = p.next
else:
h.next = q
q = q.next
h = h.next
if p:
h.next = p
if q:
h.next = q
return tmp.next
def get_mid(self, node):
if node is None:
return node
fast = slow = node
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
return slow
148. 排序链表 python
