题目
Sort a linked list in O(n log n) time using constant space complexity.
思路
- 用归并排序
- 归并排序怎么在linkedlist里面进行， 每次找重点就用slow和fast两个指针去找， 其他的合并等等和归并排序相似
Python
# 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
"""
#A intuitive solution but may be not constant space
if not head or not head.next: return head #just like the array merge-sort
# pre = ListNode(0) #use it to clear the rear half linked list
slow = fast = head #find the mid point
while fast and fast.next: #A normal way to go through the linked list using 2 pointer.
pre = slow
slow = slow.next
fast = fast.next.next
pre.next = None
return self.merge(self.sortList(head), self.sortList(slow))
def merge(self, left, right): #just like the mergesort in array, we need to merge each time
res = cur = ListNode(0) #created a new linked list to keep the merge
while left and right:
if left.val < right.val:
cur.next = left
cur = cur.next
left = left.next
else:
cur.next = right
cur = cur.next
right = right.next
if left: cur.next = left
if right: cur.next = right
return res.next
