1.题目基本信息

1.1.题目描述

给定单个链表的头 head ，使用 插入排序 对链表进行排序，并返回 排序后链表的头 。

插入排序 算法的步骤:

1. 插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。

2. 每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。

3. 重复直到所有输入数据插入完为止。

下面是插入排序算法的一个图形示例。部分排序的列表(黑色)最初只包含列表中的第一个元素。每次迭代时，从输入数据中删除一个元素(红色)，并就地插入已排序的列表中。

对链表进行插入排序。

1.2.题目地址

https://leetcode.cn/problems/insertion-sort-list/description/

2.解题方法

2.1.解题思路

插入排序

3.解题代码

python代码

# 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: Optional[ListNode]) -> Optional[ListNode]:
        if head is None:
            return head
        dumpNode = ListNode(-10000)
        dumpNode.next = head
        lastNode, node = dumpNode, head
        while node is not None:
            if node.val >= lastNode.val:
                lastNode = node
                node = lastNode.next
            else:
                # 第一步，找到最后一个小于等于node.val的节点t，t有属性：t.next最终指向第一个大于node.val的节点
                t = dumpNode
                while t.next.val <= node.val:
                    t = t.next
                # 第二步，将结点node插入t后面
                lastNode.next = node.next
                node.next = t.next
                t.next = node
                node = lastNode.next
        return dumpNode.next

4.执行结果