LeetCode147之对链表进行插入排序（相关话题：链表）

题目描述

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

插入排序 算法的步骤:

1. 插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
2. 每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
3. 重复直到所有输入数据插入完为止。

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

对链表进行插入排序。

示例 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

解题思路

1. 创建一个新的空链表（dummy node），作为已排序部分。
2. 遍历原链表，对于每一个节点，执行以下操作：
   a. 从已排序链表的头部开始，找到第一个大于或等于当前节点值的节点。
   b. 将当前节点插入到找到的节点之前。
   c. 如果当前节点是原链表的最后一个节点，那么将已排序链表的尾部节点的 next 指针指向 null。
3. 遍历结束后，已排序链表即为插入排序后的链表。

代码实现

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
 
def insertionSortList(head):
    if not head or not head.next:
        return head
 
    dummy = ListNode(-1)  # 创建一个 dummy node 作为已排序链表的头部
    cur = head
    while cur:
        next_node = cur.next  # 保存当前节点的下一个节点
        sorted_cur = dummy  # 从已排序链表头部开始遍历
        # 找到第一个大于或等于当前节点值的节点
        while sorted_cur.next and sorted_cur.next.val < cur.val:
            sorted_cur = sorted_cur.next
        # 将当前节点插入到已排序链表
        cur.next = sorted_cur.next
        sorted_cur.next = cur
        cur = next_node  # 继续遍历原链表
 
    return dummy.next  # 返回已排序链表

链表问题

LeetcCode146之LRU 缓存机制（相关话题：双向链表，哈希表）_哈希map 删除 时间复杂度 双向链表_数据与后端架构提升之路的博客-CSDN博客

LeetCode025之K 个一组翻转链表（关话题：递归，链表逆序）_数据与后端架构提升之路的博客-CSDN博客

LeetCode426之将二叉搜索树转化为排序的双向链表(相关话题：双向链表，二叉树中序)_将二进制搜索树转换为排序的循环双链表【问题描述】(利用链表二叉树)给定一个二进_数据与后端架构提升之路的博客-CSDN博客

LeetCode114之二叉树展开为链表（相关话题：二叉树，递归）_数据与后端架构提升之路的博客-CSDN博客

LeetCode之024两两交换链表中的节点（相关话题：链表递归迭代）_leetcode024_数据与后端架构提升之路的博客-CSDN博客

LeetCode142之环形链表 II（相关话题:快慢指针，绘图分析）_数据与后端架构提升之路的博客-CSDN博客

LeetCode002之两数相加（相关话题：链表操作）_数据与后端架构提升之路的博客-CSDN博客