資料結構經典：單鏈表四大核心應用——倒置、去重、合併、一元多項式相加

單鏈表應用舉例 (教科書 2.6 節精華)

1. 單鏈表倒置 (頭插法，O(n))

依次取原鏈表首節點，頭插至新鏈表 (原頭節點後)，順序自然反轉。

void reverseList(LinkList h) {
    LNode *p = h->next, *q;
    h->next = NULL;           // 置空原表
    while (p) {
        q = p;
        p = p->next;
        q->next = h->next;    // 頭插
        h->next = q;
    }
}

2. 重複節點刪除 (O(n²))

外層 p 掃描每節點，內層 q 從 p->next 向後尋找相同值節點並刪除。

void del_LinkList(LinkList h) {
    LNode *p = h->next, *q, *r;
    while (p) {
        q = p;
        while (q->next) {
            if (q->next->data == p->data) {
                r = q->next;
                q->next = r->next;
                free(r);
            } else q = q->next;
        }
        p = p->next;
    }
}

3. 兩有序單鏈表合併為非遞增表 (頭插法，O(m+n))

利用有序性，雙指標 p/q 比較，取較小者頭插至結果表 C，最後處理剩餘段。

LinkList merge_LinkList(LinkList A, LinkList B) {
    LinkList C = A; C->next = NULL; free(B);
    LNode *p = A->next, *q = B->next, *r;
    while (p && q) {
        if (p->data < q->data) { r = p; p = p->next; }
        else { r = q; q = q->next; }
        r->next = C->next; C->next = r;  // 頭插
    }
    if (!p) p = q;
    while (p) { r = p; p = p->next; r->next = C->next; C->next = r; }
    return C;
}

4. 一元多項式相加 (O(m+n))

節點含 coef (係數)、exp (指數)。雙指標 ha/hb 掃描：
• ha->exp < hb->exp：接入 ha 推進。
• ==：係數相加，非零保留 ha 刪除 hb，零則雙刪。
• >：接入 hb 推進。
剩餘段直接連接。

typedef struct LNode {
    float coef; int exp;
    struct LNode *next;
} LNode, *LinkList;

void Add(LinkList PA, LinkList PB, LinkList PC) {
    LNode *ha = PA->next, *hb = PB->next, *temp;
    PC = PA;  // 結果掛在 PA 头节点
    while (ha && hb) {
        if (ha->exp < hb->exp) {
            PC->next = ha; PC = ha; ha = ha->next;
        } else if (ha->exp == hb->exp) {
            float sum = ha->coef + hb->coef;
            if (sum != 0) {
                ha->coef = sum;
                PC->next = ha; PC = ha; ha = ha->next;
                temp = hb; hb = hb->next; free(temp);
            } else {
                temp = ha; ha = ha->next; free(temp);
                temp = hb; hb = hb->next; free(temp);
            }
        } else {
            PC->next = hb; PC = hb; hb = hb->next;
        }
    }
    PC->next = ha ? ha : hb;
    free(PB);
}

核心技巧總結

總結

單鏈表四大經典應用展示了指標操作的精髓：頭插法反序、雙指標歸併、就地修改節點連結。熟練手寫上述代碼並能現場推演指標變化，是資料結構考試、面試、系統開發的硬核基本功。