C 語言合併兩個非遞減有序線性表並去重

經典數據結構題目：已知兩個非遞減順序線性表 La、Lb，將其合併為非遞減且無重複元素的線性表 Lc。核心思路類似歸併排序的 merge 過程，但需增加去重邏輯。

演算法步驟

1. 初始化三個指針 pa、pb、pc 分別指向 La、Lb、Lc 首節點。
2. 當 pa 和 pb 均未到達表尾：
   • 若 pa->data < pb->data，將 pa 節點插入 Lc，pa 後移。
   • 若 pa->data > pb->data，將 pb 節點插入 Lc，pb 後移。
   • 若相等，僅插入一個節點，pa、pb 同時後移（去重關鍵）。
3. 將剩餘未遍歷完的表節點依序接入 Lc 尾部。
4. 釋放原 La、Lb 頭節點（若題目要求原地合併）。

關鍵代碼片段（順序表版本）

void MergeList(SqList La, SqList Lb, SqList &Lc) {
    int i = 0, j = 0, k = 0;
    Lc.length = 0;
    while (i < La.length && j < Lb.length) {
        if (La.elem[i] < Lb.elem[j]) {
            if (k == 0 || Lc.elem[k-1] != La.elem[i]) // 去重
                Lc.elem[k++] = La.elem[i];
            i++;
        } else if (La.elem[i] > Lb.elem[j]) {
            if (k == 0 || Lc.elem[k-1] != Lb.elem[j])
                Lc.elem[k++] = Lb.elem[j];
            j++;
        } else {
            if (k == 0 || Lc.elem[k-1] != La.elem[i])
                Lc.elem[k++] = La.elem[i];
            i++; j++;
        }
    }
    while (i < La.length) { if (k==0 || Lc.elem[k-1]!=La.elem[i]) Lc.elem[k++]=La.elem[i]; i++; }
    while (j < Lb.length) { if (k==0 || Lc.elem[k-1]!=Lb.elem[j]) Lc.elem[k++]=Lb.elem[j]; j++; }
    Lc.length = k;
}

完整可運行代碼可參考 此博客，包含鏈表與順序表兩種實現。