單鏈表插入操作深度解析：統一首節點與普通節點的指針技巧

單鏈表插入時，首節點需修改頭指針 `head`，其它節點修改前驅節點的 `link` 域，看似兩種情況。本文揭示 **「每個節點都有一個指向它的指針」** 這一本質，通過**指向指針的指針** 統一處理，代碼更簡潔、無特殊分支。

節點結構與根指針

typedef struct NODE {
    struct NODE *link;
    int value;
} Node;

Node *head = NULL;  // 根指針，僅含指針域

首節點由 `head` 指向，其它節點由前驅節點的 `link` 指向。**統一觀點：每個節點背後都有一個 `Node*` 類型指針變量指向它。**

統一插入算法：雙重指針遍歷

int insert(Node **linkp, int new_value) {
    Node *current;
    Node *new_node;

    // 1. 尋找插入位置：linkp 始終指向「指向當前節點的指針」
    while ((current = *linkp) != NULL && current->value < new_value)
        linkp = ¤t->link;  // 關鍵：移動到下一個節點的 link 域地址

    // 2. 分配新節點
    new_node = (Node *)malloc(sizeof(Node));
    if (!new_node) return FALSE;
    new_node->value = new_value;

    // 3. 插入：統一操作 *linkp = new_node
    new_node->link = current;
    *linkp = new_node;
    return TRUE;
}

關鍵步驟圖解

假設鏈表 `3 → 7 → 10`，插入 `5`：

1. 初始 `linkp = &head`，`*linkp` 指向節點 3。
2. 循環：`current=3`，`3<5` → `linkp = &3->link` (即 `&head` 變為 `&node3.link`)。
3. 循環：`current=7`，`7<5` 假 → 退出。此時 `linkp` 指向節點 3 的 `link` 域。
4. 插入：`new_node->link = 7`；`*linkp = new_node` → 節點 3 的 `link` 指向新節點 5。

**首節點插入同理**：`linkp` 仍為 `&head`，`*linkp = new_node` 直接修改 `head`，無需特判！

測試驗證

int main() {
    Node *head = NULL;
    Node one = {NULL, 5}, second = {NULL, 10};
    head = &one; one.link = &second;

    insert(&head, 3);  // 插入首部
    // 鏈表變為 3 → 5 → 10
}

register 優化與避坑

• 參數 `Node **linkp`、局部 `current`、`new_node` 加 `register` 提示編譯器用寄存器，減少內存訪問。
• 傳遞 `&head` 而非 `head`，實現「傳地址修改指針」。
• 循環條件 `current = *linkp` 合併賦值與判斷，簡潔高效。

核心感悟

「消除特殊情況的關鍵在於承認：首節點的前驅指針就是頭指針。」

這種「指針的指針」模式廣泛適用於鏈表刪除、查找、反轉等操作，是 C 語言指針進階的必修範式。掌握它，鏈表代碼不再充斥 `if (prev == NULL)` 分支。