C 語言單鏈表合併錯誤分析：頭插法導致順序反轉與合併邏輯缺陷

現象

合併兩個非遞減單鏈表，結果只輸出第一個結點。

根本原因

1. CreateList 使用頭插法：

   p->next = L->next;
   L->next = p;

   導致鏈表順序與輸入順序相反（輸入 1,2,3 → 鏈表 3,2,1），不再是非遞減序列，合併邏輯失效。
2. MergeList 邏輯缺陷：僅比較前 m、n 個結點后直接拼接剩余部分，未真正歸併排序。

修正方案：尾插法建表 + 標準歸併

// 尾插法建表，保持輸入順序
void CreateList(LinkList &L, int n) {
    L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;
    LinkList tail = L;
    for (int i=0; idata); // 空格跳過換行
        p->next = NULL;
        tail->next = p;
        tail = p;
    }
}

// 歸併兩有序鏈表（去重）
void MergeList(LinkList La, LinkList Lb, LinkList &Lc) {
    Lc = (LinkList)malloc(sizeof(LNode));
    LinkList pc = Lc, pa = La->next, pb = Lb->next;
    while (pa && pb) {
        if (pa->data < pb->data) {
            pc->next = pa; pa = pa->next;
        } else if (pa->data > pb->data) {
            pc->next = pb; pb = pb->next;
        } else { // 相等，取一個，雙方都前進
            pc->next = pa; pa = pa->next; pb = pb->next;
        }
        pc = pc->next;
    }
    pc->next = pa ? pa : pb; // 接上剩余部分
}

關鍵點

• 尾插法需維護 tail 指針，時間複雜度 O(1) 插入。
• 歸併邏輯類似合併排序，雙指針遍歷，構建新鏈表。
• 去重：相等時僅保留一個，雙指針同步前進。