current position:Home>leetcode 147. Insertion Sort List(python)

leetcode 147. Insertion Sort List(python)

2022-02-01 10:39:44 Wang Daya

「 This is my participation 11 The fourth of the yuegengwen challenge 26 God , Check out the activity details :2021 One last more challenge


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]
 Copy code 

Example 2:

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


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


According to the meaning , Given a one-way linked list head , Use insert sort to sort the linked list , And return the sorted list head .

Insert the steps of sorting algorithm :

  • Insert sort to iterate , Consume one input element at a time and generate a sorted output list
  • In each iteration , Insert sort removes an element from the input data , Find its location in the sort list and insert it there
  • Repeat until no input elements are left

The insertion order given by the title is rather obscure , In fact, the content of the investigation is very basic , Is the search and insertion of linked list nodes , Every time we traverse a new node , Find the place where it should be inserted in the front linked list that has been ordered , Insert the node . The key is to maintain the different pointers that need to be used , Just don't get dizzy .


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

Running results

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

Original link…

Your support is my greatest motivation

copyright notice
author[Wang Daya],Please bring the original link to reprint, thank you.

Random recommended