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

describe

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 

Note:

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

analysis

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 .

answer

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
        	      
		
 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 :leetcode.com/problems/in…

Your support is my greatest motivation

copyright notice
author[Wang Daya],Please bring the original link to reprint, thank you.
https://en.pythonmana.com/2022/02/202202011039427537.html

Random recommended