题目

147. Insertion Sort List

Sort a linked list using insertion sort.

A graphical example of insertion sort. The partial sorted list (black) initially contains only the first element in the list.

With each iteration one element (red) is removed from the input data and inserted in-place into the sorted list

Algorithm of Insertion Sort:

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.

Example 1:

Input: 4->2->1->3Output: 1->2->3->4

Example 2:

Input: -1->5->3->4->0Output: -1->0->3->4->5

解题思路

平时插入排序用的是数组，现在用链表。思路是一样的，时间复杂度还是n^2.

先创建一个空的链表，为结果链表；遍历当前链表；创建结果链表的当前位置，和下一个位置；找到需要插入当前位置的元素，在已有结果链表的位置；暂存下一个节点；以后结果链表的当前位置指向当前位置，当前位置指向结果链表的下一个位置；

# Definition for singly-linked list.class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextclass InsertionSortList:def insertionSortList(self, head: ListNode) -> ListNode:result = ListNode()current = headwhile current:# At each iteration, we insert an element into the resulting list.pre = resultnext = result.next# find the position to insert the current nodewhile next:if current.val < next.val:breakpre = nextnext = next.nextitemNext = current.next# insert the current node to the new listpre.next = currentcurrent.next = next# moving on to the next iterationcurrent = itemNextreturn result.next