單鏈表就地合併：兩個遞增鏈表合並為遞減鏈表C，頭插法巧妙逆序

問題描述

給定兩個按元素值遞增有序的單鏈表 A 和 B（帶頭結點），要求將其合併為一個按元素值遞減有序（非遞增）的單鏈表 C，**不允許申請新結點，必須利用原表結點空間**構造 C 表。

核心洞見：頭插法天然逆序

常規合併有序鏈表采用尾插法保持遞增。本題要求遞減，只需在合併過程中改用頭插法：每次取出較小的結點，插入到 C 表頭結點之後。由於先取出的較小元素先插入表頭，後取出的較大元素又插在它們前面，最終 C 表自然呈現遞減順序——「合併即逆序，一舉兩得」。

完整 C 代碼實現

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2

#include <stdio.h>
#include <malloc.h>

typedef int ElemType;
typedef int Status;

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

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

// 初始化帶頭結點的空表
void InitList(LinkList *L) {
    *L = (LinkList)malloc(sizeof(LNode));
    (*L)->next = NULL;
}

// 核心合併算法：頭插法構造遞減表 C
Status Merger_AandB_toC(LinkList *La, LinkList *Lb, LinkList *Lc) {
    LinkList pa, pb, qa, qb;
    (*Lc)->next = NULL;  // C 表初始為空
    qa = *La; qb = *Lb;  // qa/qb 保留前驅，便於斷鏈
    pa = (*La)->next;    // pa/pb 為工作指針
    pb = (*Lb)->next;

    while (pa && pb) {
        if (pa->data < pb->data) {  // 取較小者
            qa = pa;
            pa = pa->next;
            qa->next = (*Lc)->next;  // 頭插到 C 表
            (*Lc)->next = qa;
        } else {
            qb = pb;
            pb = pb->next;
            qb->next = (*Lc)->next;
            (*Lc)->next = qb;
        }
    }
    // 剩餘結點批量頭插
    if (!pa) while (pb) { qb = pb; pb = pb->next; qb->next = (*Lc)->next; (*Lc)->next = qb; }
    if (!pb) while (pa) { qa = pa; pa = pa->next; qa->next = (*Lc)->next; (*Lc)->next = qa; }
    return OK;
}

int main() {
    LinkList La, Lb, Lc, p;
    InitList(&La);
    printf("請輸入La元素(0結束):\n");
    CreateList_TailInsert(&La);
    // 打印La...
    InitList(&Lb);
    printf("請輸入Lb元素(0結束):\n");
    CreateList_TailInsert(&Lb);
    // 打印Lb...
    InitList(&Lc);
    Merger_AandB_toC(&La, &Lb, &Lc);
    // 打印Lc...
    return 0;
}

圖解關鍵步驟（以 La: 1→3→5, Lb: 2→4→6 為例）

1. 比較 1 和 2，取 1 頭插 C：C = 1
2. 比較 3 和 2，取 2 頭插 C：C = 2→1
3. 比較 3 和 4，取 3 頭插 C：C = 3→2→1
4. ... 最終 C = 6→5→4→3→2→1，完美遞減

複雜度與空間優勢

• 時間 O(m+n)：雙指針單次掃描，無回溯。
• 空間 O(1)：僅使用常數額外指針，**零新結點分配**，完美滿足「利用原表空間」要求。

避坑提示

• 頭插法中 qa->next = (*Lc)->next; (*Lc)->next = qa; 兩步順序不可顛倒，否則丟失鏈表。
• 合併後 La、Lb 原鏈表結構已被破壞（結點已移至 C），若後續仍需使用原表，請提前深拷貝。
• 畫圖輔助理解指針跳轉，紙上推演一次勝過腦補十遍。