leetcode 147. Insertion Sort List(python)

語言: CN / TW / HK



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]


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
            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.