148. Sort List

题目

Sort a linked list in O(n log n) time using constant space complexity.

思路

1. 用归并排序
2. 归并排序怎么在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