動機

merge sort的所有case都是O(nLog(n))!!

Problem

Given the head of a linked list, return the list after sorting it in ascending order.

Follow up: Can you sort the linked list in O(n logn) time and O(1) memory (i.e. constant space)?

 

Example 1:

Input: head = [4,2,1,3]Output: [1,2,3,4]

Example 2:

Input: head = [-1,5,3,4,0]Output: [-1,0,3,4,5]

Example 3:

Input: head = []Output: []

 

Constraints:

  • The number of nodes in the list is in the range [0, 5 * 104].
  • -105 <= Node.val <= 105

Sol

當初是先用qsort去寫，結果在極端與大的case吃鱉

因為選的pivot通常不是好的，所以吃了一堆TLE

所以要用merge sort

def havle(r):
    ptr = r
    mid = r
    endLeft = None
    while ptr and ptr.next:
        endLeft = mid
        mid = mid.next
        ptr = ptr.next.next
    right = mid
    endLeft.next = None
    return [r, right]
def sort(r):
    if not r or not r.next:
        return r
    left, right = havle(r)
    left = sort(left)
    right = sort(right)
    
    ret = ListNode()
    ptr = ret
    while left or right:
        if left and right:
            if left.val <= right.val:
                ptr.next = left
                left = left.next
            else:
                ptr.next = right
                right = right.next
            ptr = ptr.next
        elif left:
            ptr.next = left
            break
        else:
            ptr.next = right
            break
    return ret.next
class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        return sort(head)