148. 排序链表
在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
示例:
输入: 4->2->1->3
输出: 1->2->3->4
解法1
采用归并排序, 先找到链表的中间的一分为二, 左右两个链表分别归并排序, 再将排好序的链表合并.
class Solution(object):
def sortList(self, head):
if head == None or head.next == None:
return head
half = self.halfList(head)
li, ri = head, half.next
half.next = None
li = self.sortList(li)
ri = self.sortList(ri)
pre = ListNode(-1)
tail = pre
while li != None and ri != None:
if li.val < ri.val:
tail.next = li
li = li.next
else:
tail.next = ri
ri = ri.next
tail = tail.next
if li != None:
tail.next = li
else:
tail.next = ri
return pre.next
def halfList(self, head):
if head == None or head.next == None:
return head
fast = head
slow = head
while fast.next != None and fast.next.next != None:
slow, fast = slow.next, fast.next.next
return slow
解法2
也是采用归并排序, 运用递归的思想和一个合并两个链表的方法.
class Solution(object):
def sortList(self, head):
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
