The title
Links:Leetcode-cn.com/problems/in…
thinking
Insert sort is one of the three simple sorts, with the following pseudocode:
INSERTION-SORT(A) //A is an arrayfor j = 2To a.length key = A[j] // insert A[j] into A[1..j-1])
i = j - 1
while i > 0 and A[i] > key
A[i+1] = A[i]
i = i - 1
A[i+1] = key
Copy the code
In the insertion sort template, we search for the position of A[j] from back to front, moving each number back one bit as we search. This problem basically does not need to change the insert sort template, but in the linked list we have to start from scratch.
Answer key
PrevNode in the following code represents the sort sequence A[1…j-1] in the template, and head is j = 2 to a. length for the template’s outer loop. While prevnode. next and prevnode.next-val < head. Val: prevNode is the last node less than head after this loop. Prevnode. val < head. Val < prevNode.next-val. So head points to the larger element prevNode.next, prevNode points to head. It should be noted that before the operation of the linked list, the next element of head should be stored in the NXT first. After the operation of the linked list, head = NXT, so as to ensure the circulation.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def insertionSortList(self, head: ListNode) -> ListNode:
if not head: return head
dummy = ListNode(0)
prev = head
while head:
prevNode = dummy
while prevNode.next and prevNode.next.val < head.val:
prevNode = prevNode.next
nxt = head.next
head.next = prevNode.next
prevNode.next = head
head = nxt
return dummy.next
Copy the code
The resources
[1] blog.csdn.net/weixin_4336…