LeetCode 147. 對鏈表進行插入排序：四指針原地插入實現

LeetCode 147. 對鏈表進行插入排序

題目要求

對單向鏈表進行**插入排序**，返回排序後鏈表頭。原地操作，不分配新節點。

算法思想

維護「已排序部分」與「未排序部分」。每次從未排序部分取出一個節點 insert，在已排序部分找到插入位置並插入。需四指針協作：

• insert_p：待插入節點的前驅（未排序部分已處理尾部）。
• insert：待插入節點。
• cur：已排序部分掃描指針。
• cur_p：cur 的前驅（插入位置前驅）。

完整代碼

struct ListNode* insertionSortList(struct ListNode* head) {
    if (!head) return NULL;
    
    struct ListNode *insert_p = head;
    struct ListNode *insert = head->next;
    
    while (insert) {
        struct ListNode *cur = head;
        struct ListNode *cur_p = head;
        int inserted = 0;
        
        while (cur != insert) {
            if (head->val > insert->val) {           // 插入頭部
                insert_p->next = insert->next;
                insert->next = head;
                head = insert;
                insert = insert_p->next;
                inserted = 1;
                break;
            }
            else if (cur->val > insert->val) {       // 插入中間
                insert_p->next = insert->next;
                cur_p->next = insert;
                insert->next = cur;
                insert = insert_p->next;
                inserted = 1;
                break;
            }
            cur_p = cur;
            cur = cur->next;
        }
        
        if (!inserted) {                             // 無需插入，已有序
            insert_p = insert;
            insert = insert->next;
        }
    }
    return head;
}

關鍵細節解析

• 插入頭部特判：需更新 head，順序為：斷開 insert → insert->next = head → head = insert。
• 插入中部：cur_p->next = insert; insert->next = cur;。
• 斷開原位置：insert_p->next = insert->next; 必須在插入前執行，否則環路。
• inserted 標志：區分「已插入（insert 已推進）」與「未插入（需推進 insert_p 和 insert）」。

複雜度分析

• 時間：O(n²)，插入排序固有複雜度（鏈表無法二分查找插入位置）。
• 空間：O(1)，原地排序。

優化方向（了解即可）

• 維護已排序部分尾指針，若 insert->val >= tail->val 直接尾插，避免掃描。
• 歸併排序可達 O(n log n)，但遞歸棧空間 O(log n)，或迭代版 O(1) 空間（較複雜）。

總結

鏈表插入排序是「有序鏈表插入節點」的重複應用。四指針 insert_p/insert/cur/cur_p 精確控制「斷開、尋址、插入、推進」四步驟，是指針操作基本功的優秀練習。掌握「虛擬頭節點統一頭部插入邏輯」可進一步簡化代碼。