演算法實戰：合併兩個遞增單鏈表為遞減單鏈表（原地操作、O(1) 空間）

題目重述

給定兩個遞增有序的單鏈表 A、B（含頭節點），要求將其合併為一個遞減有序（非遞增）單鏈表 C，且不得申請新節點，必須利用 A、B 原有節點空間構造 C。

核心思路：頭插法構建逆序

由於 A、B 本身是遞增（由小到大），若按歸併排序邏輯依序取較小節點，產生的順序仍是遞增。要得到遞減，只需在取出節點時採用頭插法：每次將選出的節點插入 C 表頭部，最終 C 自然呈現遞減順序。

演算法步驟

1. 初始化 C 為空表（僅頭節點，C->next = NULL）。
2. 雙指標 pa、pb 分別指向 A、B 首個資料節點；qa、qb 保留前驅以便斷鏈。
3. 當 pa 與 pb 均非空：
   • 比較 pa->data 與 pb->data，取較小者（假設為 pa）。
   • qa = pa; pa = pa->next; 斷開該節點。
   • 頭插入 C：qa->next = C->next; C->next = qa;
4. 若一表耗盡，將另一表剩餘節點依序頭插入 C。
5. 最終 C 即為遞減有序單鏈表，A、B 原頭節點仍在但 next 為空。

完整 C 實作（含建表、列印、主程式）

#include 
#include 

#define TRUE  1
#define FALSE 0
#define OK    1
#define ERROR 0

typedef int ElemType;
typedef int Status;

typedef struct LNode {
    ElemType data;
    struct LNode *next;
} LNode, *LinkList;

// 初始化帶頭節點的空單鏈表
Status InitList(LinkList *L) {
    *L = (LinkList)malloc(sizeof(LNode));
    if (!*L) return ERROR;
    (*L)->next = NULL;
    return OK;
}

// 尾插法建表（輸入 0 結束）
void CreateList_TailInsert(LinkList *L) {
    LinkList p, r = *L;  // r 指向尾節點
    int val;
    while (scanf("%d", &val) == 1 && val != 0) {
        p = (LinkList)malloc(sizeof(LNode));
        if (!p) exit(EXIT_FAILURE);
        p->data = val;
        r->next = p;
        r = p;
    }
    r->next = NULL;
}

// 核心合併演算法：升序 A、B → 降序 C（原地）
Status Merge_IncreasingToDecreasing(LinkList *La, LinkList *Lb, LinkList *Lc) {
    LinkList pa = (*La)->next, pb = (*Lb)->next;
    LinkList qa, qb;

    (*Lc)->next = NULL;  // C 初始為空

    while (pa && pb) {
        if (pa->data < pb->data) {
            qa = pa;
            pa = pa->next;
            qa->next = (*Lc)->next;
            (*Lc)->next = qa;
        } else {
            qb = pb;
            pb = pb->next;
            qb->next = (*Lc)->next;
            (*Lc)->next = qb;
        }
    }
    while (pa) {  // A 剩餘
        qa = pa;
        pa = pa->next;
        qa->next = (*Lc)->next;
        (*Lc)->next = qa;
    }
    while (pb) {  // B 剩餘
        qb = pb;
        pb = pb->next;
        qb->next = (*Lc)->next;
        (*Lc)->next = qb;
    }
    return OK;
}

// 列印鏈表（跳過頭節點）
void PrintList(LinkList L) {
    LinkList p = L->next;
    while (p) {
        printf("%d ", p->data);
        p = p->next;
    }
    putchar('\n');
}

int main(void) {
    LinkList La, Lb, Lc;

    InitList(&La);
    printf("請輸入遞增序列 A（以 0 結束）：\n");
    CreateList_TailInsert(&La);
    printf("A: "); PrintList(La);

    InitList(&Lb);
    printf("請輸入遞增序列 B（以 0 結束）：\n");
    CreateList_TailInsert(&Lb);
    printf("B: "); PrintList(Lb);

    InitList(&Lc);
    Merge_IncreasingToDecreasing(&La, &Lb, &Lc);
    printf("合併後遞減序列 C: ");
    PrintList(Lc);

    // 釋放記憶體（略）
    return 0;
}

複雜度分析

圖解關鍵步驟（頭插法）

初始:  A: 1→3→5    B: 2→4→6    C: (head)→NULL

取 A(1):  qa=1, pa→3
          1→NULL
          C: (head)→1→NULL

取 B(2):  qb=2, pb→4
          2→1→NULL
          C: (head)→2→1→NULL

取 A(3):  3→2→1→NULL
          C: (head)→3→2→1→NULL
... 以此類推，最終 C: 6→5→4→3→2→1

易錯點提醒

• ❌ 忘記先保存 pa->next 再斷鏈，導致鏈表斷裂。
• ❌ 使用尾插法（需維護尾指標），結果會是遞增而非遞減。
• ❌ 合併後未將 A、B 頭節點 next 設為 NULL，殘留指標造成邏輯錯誤。
• ✅ 畫圖推演是掌握指標操作的最佳方式，建議面試前手寫數次。

延伸變體

• 若要求合併為遞增且不可破壞原表 → 需申請新節點複製資料，空間 O(m+n)。
• 若為循環單鏈表 → 需處理尾節點指向頭節點的邏輯。
• 若為雙向鏈表 → 同步維護 prior 指標。