# Definition for singly-linked list.# class ListNode:# def __init__(self, val=0, next=None):# self.val = val# self.next = nextclassSolution:definsertionSortList(self,head:ListNode)->ListNode:dummy=ListNode(0)# 哑结点，dummy.next 是已排序部分cur=headwhilecur:# 在已排序链表中找到插入位置prev=dummywhileprev.nextandprev.next.val<=cur.val:prev=prev.next# 保存下一个待处理节点nxt=cur.next# 把 cur 插入到 prev 之后cur.next=prev.nextprev.next=cur cur=nxtreturndummy.next思路
和数组插入排序一样，维护一个有序部分，每次从原链表取一个节点，插入到有序部分的正确位置。
· dummy 是哑结点，dummy.next 指向已排序链表的头部，避免处理“插入到头部”的边界。
· 对每个 cur，从 dummy 往后找，找到最后一个值小于等于 cur.val 的节点 prev。
· 把 cur 插到 prev 后面。
· 注意先保存 nxt = cur.next，因为后面会修改 cur.next。
使用 <= 可以保持稳定性：相等元素维持原有相对顺序。
复杂度
· 时间：O(n²)，最坏情况下每个节点都要从头扫描已排序部分。
· 空间：O(1)，原地排序，只用常数个指针。
测试
defprint_list(head):vals=[]whilehead:vals.append(head.val)head=head.nextprint(vals)# 4 -> 2 -> 1 -> 3head=ListNode(4,ListNode(2,ListNode(1,ListNode(3))))print_list(Solution().insertionSortList(head))# [1, 2, 3, 4]# -1 -> 5 -> 3 -> 4 -> 0head=ListNode(-1,ListNode(5,ListNode(3,ListNode(4,ListNode(0)))))print_list(Solution().insertionSortList(head))# [-1, 0, 3, 4, 5]
