LeetCode 147 Insertion Sort List：鏈表插入排序實現

問題描述

對單鏈表進行插入排序，要求 O(1) 額外空間。

算法思路

維護一個已排序的虛擬頭節點 preHead。遍歷原鏈表，對每個節點 cur，在已排序部分鏈表中找到插入位置（第一個值 ≥ cur->val 的節點之前），插入。

代碼實現

ListNode* insertionSortList(ListNode* head) {
    ListNode preHead(-1);
    while (head) {
        ListNode* cur = &preHead;
        int val = head->val;
        while (cur->next && cur->next->val < val) cur = cur->next;
        ListNode* nxt = head->next;
        head->next = cur->next;
        cur->next = head;
        head = nxt;
    }
    return preHead.next;
}

複雜度

• 時間：O(n²) 最壞/平均，O(n) 最好（已有序）。
• 空間：O(1) 額外空間。

關鍵細節

• 使用 preHead 統一處理頭部插入。
• 先保存 head->next 再斷開插入，避免丟失後續節點。
• 內層循環條件 cur->next->val < val 保證穩定性（相等值插在後面）。