题目描述
对链表进行插入排序。
插入排序的动画演示如上。从第一个元素开始，该链表可以被认为已经部分排序（用黑色表示）。
每次迭代时，从输入数据中移除一个元素（用红色表示），并原地将其插入到已排好序的链表中。
image
插入排序算法：
插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
重复直到所有输入数据插入完为止。
示例 1：
输入: 4->2->1->3
输出: 1->2->3->4
示例 2：
输入: -1->5->3->4->0
输出: -1->0->3->4->5
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/insertion-sort-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题思路
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def insertionSortList(self, head: ListNode) -> ListNode:
if not head or (head.next is None):
return head
newhead = ListNode(0)
newhead.next = head
premove, nextmove= newhead,newhead.next
rsulthead = newhead
prehead, curhead = newhead.next,newhead.next.next
# curhead 为循环对象
while curhead :
# curhead 之前的节点是有序的 寻找 第一个大于curhead 的节点
while nextmove.val < curhead.val :
# print("nextmvoe.val:curhead.val=",nextmove.val,curhead.val)
nextmove = nextmove.next
premove = premove.next
if nextmove == curhead :
# 这时
prehead =prehead.next
curhead = curhead.next
# 重置premove nextmove
premove, nextmove= newhead,newhead.next
continue
# 在nextmove节点之前插入 curhead节点
temp = curhead
prehead.next = curhead.next # 防止链表断开
temp.next = nextmove # 插入 curhead节点
premove.next = temp
curhead = prehead.next
# 重置premove nextmove
premove, nextmove= newhead,newhead.next
return newhead.next
问题不在于没有思路，而是有了思路，实现细节把握不了。刚开始凭感觉写，后来分析以下发现：
在节点插入的地方需要有两个指针，一个指向插入之前的节点premove，一个指向插入之后的节点nextmove。
在循环的节点处需要有两个指针，一个指向循环节点curhead，一个指向循环节点之前prehead。
另外需要在链表头新插入一个头，以防止每次在表头插入节点的时候无法返回链表头。
这时就是我上述的代码
但是可以更近一步 因为两个指针可以用一个来代替，即 pre 和pre.next 但是需要每次做判断的时候都用pre.next 来判断，就可以保持有一个pre可以用，不需要重新设置一个指针。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def insertionSortList(self, head: ListNode) -> ListNode:
if not head or not head.next:
return head
dummy = ListNode(0)
dummy.next = head
while head and head.next:
if head.val <=head.next.val:
head = head.next
continue
pre = dummy
while pre.next.val<head.next.val:
pre = pre.next
#每次找到Next的位置，不需要每次进行移动
Next = head.next
head.next = Next.next
Next.next = pre.next
pre.next = Next
return dummy.next
641a6f49b553c522166a0b4b455c78c.png
