难度: Medium
给定单个链表的头 head ，使用 插入排序 对链表进行排序，并返回 排序后链表的头 。
插入排序 算法的步骤:
下面是插入排序算法的一个图形示例。部分排序的列表(黑色)最初只包含列表中的第一个元素。每次迭代时，从输入数据中删除一个元素(红色)，并就地插入已排序的列表中。
对链表进行插入排序。
示例 1：
输入: head = [4,2,1,3] 输出: [1,2,3,4]
示例 2：
输入: head = [-1,5,3,4,0] 输出: [-1,0,3,4,5]
提示：
[1, 5000]范围内-5000 <= Node.val <= 5000运行时间: 192 ms
内存: 16.5 MB
# 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: ListNode) -> ListNode:
if head is None or head.next is None:
return head
dummy = ListNode(next=head)
last_sorted = head
cur = head.next
while cur:
if cur.val > last_sorted.val:
last_sorted = last_sorted.next
else:
pre = dummy
while pre.next.val < cur.val:
pre = pre.next
last_sorted.next = cur.next
cur.next = pre.next
pre.next = cur
cur = last_sorted.next
return dummy.next
该题解使用插入排序的思想对链表进行排序。具体步骤如下： 1. 首先判断链表是否为空或者只有一个节点，如果是则直接返回。 2. 创建一个虚拟头节点dummy，指向原始链表的头节点。 3. 用last_sorted表示已排序部分的最后一个节点，初始为头节点。 4. 用cur表示当前需要插入的节点，初始为头节点的下一个节点。 5. 遍历cur节点，对于每个cur节点： - 如果cur节点的值大于last_sorted节点的值，说明cur应该插入到已排序部分的最后，将last_sorted后移一位。 - 否则，从dummy节点开始遍历已排序部分，找到第一个大于cur的节点pre，将cur插入到pre之前。 6. 重复步骤5直到cur为空。 7. 返回dummy.next作为排序后的链表头节点。
时间复杂度: O(n^2)
空间复杂度: O(1)
# 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: ListNode) -> ListNode:
# 特殊情况：空链表或只有一个节点，直接返回
if head is None or head.next is None:
return head
# 创建虚拟头节点，指向原始链表头
dummy = ListNode(next=head)
# last_sorted是已排序部分的最后一个节点，初始为原始链表头
last_sorted = head
# cur是当前需要插入的节点
cur = head.next
while cur:
# 若cur大于已排序部分的最后一个，则cur应插入到最后
if cur.val > last_sorted.val:
last_sorted = last_sorted.next
else:
# 否则，从链表头开始找第一个大于cur的节点pre
pre = dummy
while pre.next.val < cur.val:
pre = pre.next
# 将cur从原位置移除，插入到pre之后
last_sorted.next = cur.next
cur.next = pre.next
pre.next = cur
cur = last_sorted.next
# 返回排序后的链表的头节点
return dummy.next
使用虚拟头节点`dummy`的主要原因是为了简化插入到链表头部的操作。在插入排序过程中，如果新的节点需要插入到当前所有已排序节点之前，使用虚拟头节点可以避免额外的条件判断来处理头节点的变化。如果直接使用原链表的头节点，每次插入到头部时都需要更新头节点，这会增加代码的复杂度并可能导致错误。
在将`cur`节点插入到新位置前，先将`cur`节点从其当前位置断开，这是通过设置`last_sorted.next`指向`cur.next`来完成的。然后，将`cur`插入到新的位置，这是通过设置`cur.next`指向`pre.next`，再将`pre.next`指向`cur`来完成的。这样的操作确保了在操作过程中，所有节点都被正确地维持和连接，没有任何节点会丢失。
当`cur`的值小于`last_sorted`的值时，这表示`cur`需要被插入到已排序部分的某个位置，并非仅仅是`last_sorted`之后。因为`last_sorted`代表已排序部分的末尾，所以从`last_sorted`开始向前寻找会增加复杂性，并且可能需要额外的指针来追踪。从虚拟头节点`dummy`开始遍历可以线性地遍历已排序部分，简化了逻辑并且保证能找到正确的插入位置。
如果`cur`节点需要插入到`last_sorted`之前的某个位置，意味着`cur`节点原来的位置不再是其在排序链表中的正确位置。因此，需要将`cur`节点从原位置移除，即断开`last_sorted`与`cur`之间的链接，然后将`cur`插入到正确的位置。这样的操作是为了保持链表的顺序性和正确性。