LeetCode 链表插入排序：哨兵节点 + 就地重排

题目要求

对单链表进行插入排序，返回排序后头节点。插入排序：每步取一个待排节点，插入已排序部分的合适位置。

算法思路

• 创建哨兵节点 helper 作为已排序部分的虚拟头
• 遍历原链表，每取一节点 cur，在已排序链表中找到插入位置 pre
• 将 cur 插入 pre 之后，继续处理下一节点

C++ 实现

class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        if (!head || !head->next) return head;
        ListNode* helper = new ListNode(0); // 哨兵
        ListNode* cur = head;
        while (cur) {
            ListNode* next = cur->next; // 保存下一节点
            ListNode* pre = helper;
            // 找到插入位置：pre->next 为首个大于 cur->val 的节点
            while (pre->next && pre->next->val < cur->val)
                pre = pre->next;
            // 插入
            cur->next = pre->next;
            pre->next = cur;
            cur = next;
        }
        ListNode* res = helper->next;
        delete helper;
        return res;
    }
};

复杂度分析

• 时间：O(n²) 最坏/平均，O(n) 最好（已有序）
• 空间：O(1) 额外空间（仅哨兵节点）

关键技巧

1. 哨兵节点：统一处理头节点插入，避免特判
2. 预存 next：插入会修改 cur->next，必须先保存
3. 就地重排：不创建新节点，直接调整指针

对比：数组插入排序

void insertionSort(vector& a) {
    for (int i = 1; i < a.size(); ++i) {
        int key = a[i], j = i - 1;
        while (j >= 0 && a[j] > key) a[j+1] = a[j--];
        a[j+1] = key;
    }
}

链表版无需移动元素，仅调整指针，但无法二分查找插入位置（无随机访问），故仍为 O(n²)。