题目描述

对链表进行插入排序。

插入排序的动画演示如上。从第一个元素开始，该链表可以被认为已经部分排序（用黑色表示）。
每次迭代时，从输入数据中移除一个元素（用红色表示），并原地将其插入到已排好序的链表中。

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