leetcode 147. Insertion Sort List(python)

語言: CN / TW / HK

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

描述

Given the head of a singly linked list, sort the list using insertion sort, and return the sorted list's head.

The steps of the insertion sort algorithm:

  • Insertion sort iterates, consuming one input element each repetition and growing a sorted output list.
  • At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list and inserts it there.
  • It repeats until no input elements remain.

The following is a graphical example of the insertion sort algorithm. The partially sorted list (black) initially contains only the first element in the list. One element (red) is removed from the input data and inserted in-place into the sorted list with each iteration.

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]

Note:

The number of nodes in the list is in the range [1, 5000].
-5000 <= Node.val <= 5000

解析

根據題意,給定一個單向連結串列 head ,使用插入排序對連結串列進行排序,並返回排序後的列表 head 。

插入排序演算法的步驟:

  • 插入排序進行迭代,每次重複消耗一個輸入元素並生成一個排序的輸出列表
  • 在每次迭代中,插入排序從輸入資料中刪除一個元素,在排序列表中找到它所屬的位置並將其插入到那裡
  • 重複直到沒有輸入元素剩餘

題目給出的插入排序比較晦澀,其實考察的內容很基礎,就是對連結串列節點的搜尋和插入,我們每遍歷一個新的節點,找到其在已經排好序的前面的連結串列中應該插入的位置,進行節點的插入操作即可。關鍵是要維護好需要用的不同指標,別被繞暈了就行。

解答

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

執行結果

Runtime: 172 ms, faster than 81.63% of Python online submissions for Insertion Sort List.
Memory Usage: 17.2 MB, less than 15.65% of Python online submissions for Insertion Sort List.

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

您的支援是我最大的動力