資料結構：稀疏多項式單鏈表建立中 q 指標的作用詳細解析

演算法背景

稀疏多項式以單鏈表儲存，每項包含係數、指數。建立過程中需按指數遞減序插入新節點。教材演算法引入 `q` 指標，初學者不解其用途。

q 指標的核心作用

`q` 是**工作指標**，始終指向**當前插入位置的後繼節點**（即新節點未來的 `next`）。配合 `pre`（前驅指標），完成「找位置、鏈接」兩步驟。

逐輪演示

// 假設頭節點 P，pre、q、s 均為指標
// 第 1 輪插入第一個節點（i=0）
pre = P;           // pre 指向頭節點
q = P->next;       // q 指向 NULL（空表）
while(...) 不滿足
s->next = q;       // 新節點 next 指向 NULL
pre->next = s;     // 頭節點 next 指向新節點 s

// 第 2 輪插入第二個節點（i=1）
pre = P;           // 重置 pre 到頭節點
q = P->next;       // q 指向第一個節點 s
while(條件滿足) {  // 找到插入位置
    pre = q;       // pre 移動到第一個節點
    q = q->next;   // q 移動到 NULL（或下一個節點）
}
s->next = q;       // 新節點 next 指向 q（NULL 或後續節點）
pre->next = s;     // pre（第一個節點）next 指向新節點

pre 的三重角色

1. **重置起點**：每輪 `pre = P`，確保從頭遍歷。
2. **遍歷游標**：`while` 迴圈中 `pre = q` 逐步後移，尋找插入位置的前驅。
3. **鏈接操作**：`pre->next = s` 將新節點接入鏈表。

總結

`q` 並非多餘，它**隨時保存「插入點之後的節點」**，使 `s->next = q` 成為統一操作，無論插在表頭、表尾、中間，邏輯一致。這是鏈表插入的經典「雙指標（pre/q）協作」模式。