leetcode 148. Sort List(python)

語言: CN / TW / HK

「這是我參與11月更文挑戰的第29天,活動詳情檢視:2021最後一次更文挑戰

描述

Given the head of a linked list, return the list after sorting it in ascending order.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: []

Note:

The number of nodes in the list is in the range [0, 5 * 10^4].
-10^5 <= Node.val <= 10^5

解析

根據題意,就是給出了一個連結串列的頭節點 head ,要求我們對其進行升序排序。題目還要求我們使用 O(n logn) 的時間複雜度和 O(1) 的記憶體。我嘗試用了最簡單的暴力插入,空間複雜度還是 O(1),但是 O(n^2) 時間複雜度,還是超時了。

解答

class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution(object):
    def sortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head or not head.next:return head
        L = ListNode(val=-1000000)
        L.next  = cur = head
        while cur.next:
            pre = L
            if cur.next.val >= cur.val:
                cur = cur.next
                continue
            while pre.next.val < cur.next.val:
                pre = pre.next
            tmp  = cur.next
            cur.next = tmp.next
            tmp.next = pre.next
            pre.next = tmp
        return L.next

執行結果

Time Limit Exceeded

解析

因為這裡用到了內建函式 sorted 對值進行排序,又重新建立新的連結串列,所以時間上覆雜度上是 O(n logn) 但是竟然通過了汗顏。但是空間複雜度是 O(n)。

解答

class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution(object):
    def sortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head or not head.next:
            return head
        node = ListNode(val = 0)
        result = node
        nlist = []
        while head != None:
            nlist.append(head.val)
            head = head.next
        nlist = sorted(nlist)
        for n in nlist:
            node.next = ListNode(val = n)
            node = node.next
        return result.next

執行結果

Runtime: 284 ms, faster than 84.91% of Python online submissions for Sort List.
Memory Usage: 63.3 MB, less than 12.52% of Python online submissions for Sort List.

解析

還可以用歸併排序,只要是時間複雜度為 O(n logn) 的其他排序演算法都可以。

解答

class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution(object):
    def sortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head or not head.next:return head
        mid = self.getMid(head)
        another = mid.next
        mid.next = None
        return self.merge(self.sortList(head), self.sortList(another))

    def getMid(self, head):
        fast = slow = head
        while fast.next and fast.next.next:
            fast = fast.next.next
            slow = slow.next
        return slow

    def merge(self, A, B):
        dummy = cur = ListNode(0)
        while A and B:
            if A.val > B.val:
                cur.next = B
                B = B.next
            else:
                cur.next = A
                A = A.next
            cur = cur.next
        if A: cur.next = A
        if B: cur.next = B
        return dummy.next

執行結果

Runtime: 544 ms, faster than 44.25% of Python online submissions for Sort List.
Memory Usage: 45.6 MB, less than 86.45% of Python online submissions for Sort List.

原題連結:https://leetcode.com/problems/sort-list/

您的支援是我最大的動力