ソート1.Sort List

leetcode 148. Sort List
質問する
接続リストをO(n logn)に揃えます.
I/O例

入力:4、2、1、3

出力:1、2、3、4

に答える
O(n log n)の時間的複雑さが制限されるため,複数のソート方法が用いられるため,ブールソートは用いられない.したがって,並べ替えと関数を内蔵する方法を用いて解くことができる.
連結ソート

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if l1 and l2:
            if l1.val > l2.val:
                l1, l2 = l2, l1
            l1.next = self.mergeTwoLists(l1.next, l2)
        return l1 or l2

    def sortList(self, head: ListNode) -> ListNode:
        if not (head and head.next):
            return head

        half, slow, fast = None, head, head
        while fast and fast.next:
            half, slow, fast = slow, slow.next, fast.next.next
        half.next = None

        l1 = self.sortList(head)
        l2 = self.sortList(slow)

        return self.mergeTwoLists(l1, l2)

runtime: 572 ms

memory: 50.9 MB

ソートチーム

class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        p = head
        lst: List = []
        while p:
            lst.append(p.val)
            p = p.next

        lst.sort()

        p = head
        for i in range(len(lst)):
            p.val = lst[i]
            p = p.next
        return head

runtime: 160 ms

memory: 30.1 MB

Python内蔵関数sort()を使用すると、直接集計ソートを実現するよりも実際のソート速度が速いことがわかります.
リファレンス
Pythonアルゴリズムインタビュー