資料結構教材實作：單鏈表歸並（鏈式儲存）

資料結構教材實作：單鏈表歸並（鏈式儲存）

核心優勢

鏈式儲存歸並無需移動元素，僅需修改指標指向，避免了順序表歸並時大量元素後移的開銷，時間複雜度仍為 O(m+n) 但常數因子極小。

插入操作示意

關鍵程式碼 (MergeList.c)

void MergeList(LinkList &La, LinkList &Lb, LinkList &Lc) {
    LinkList pa = La->next, pb = Lb->next, pc;
    Lc = pc = La;  // 利用 La 的頭節點作為 Lc 頭節點
    while (pa && pb) {
        if (pa->data <= pb->data) {
            pc->next = pa; pc = pa; pa = pa->next;
        } else {
            pc->next = pb; pc = pb; pb = pb->next;
        }
    }
    pc->next = pa ? pa : pb;  // 鏈接剩餘段
    free(Lb);  // 釋放 Lb 頭節點
}

測試資料與結果

• TestData_HL.txt：頭插法建表資料
• TestData_TL.txt：尾插法建表資料

檔案清單

• MergeList.h/c：歸並演算法
• MergeList-main.c：主程式
• 兩組測試資料檔

本範例完整呈現鏈式歸並的指標操作細節，是掌握鏈表指標操作的經典練習。