鏈表進階操作：倒數第K個節點與有序鏈表合併（遞歸與非遞歸）

前言

本文解決兩個經典鏈表問題：查找倒數第K個節點、合併兩個有序鏈表。後者提供遞歸與非遞歸兩種實現，展示不同算法思路的優劣權衡。

一、節點結構定義

typedef struct node {
    int data;
    struct node *next;
} Linknode;

二、問題一：查找倒數第K個節點（雙指針法）

核心思路

使用兩個指標 fast 和 slow，fast 先走 K-1 步，然後雙指針同步前進，當 fast 到達尾節點時，slow 即指向倒數第K個節點。

完整實現

bool findLastKnode(Linknode* head, int k) {
    assert(head != NULL && k > 0);
    Linknode *fast = head, *slow = head;
    int step = 1;
    
    // 1. fast 先走 k-1 步
    while (fast != NULL && step < k) {
        fast = fast->next;
        step++;
    }
    
    // 2. 邊界檢查：鏈表長度不足 k
    if (step != k || fast == NULL) {
        printf("鏈表長度不足 %d 個節點\n", k);
        return false;
    }
    
    // 3. 雙指針同步前進，直到 fast 到達最後一個節點
    while (fast->next != NULL) {
        fast = fast->next;
        slow = slow->next;
    }
    
    printf("倒數第 %d 個節點值: %d\n", k, slow->data);
    return true;
}

複雜度分析

• 時間：O(n) — 單次遍歷
• 空間：O(1) — 僅使用兩個指標

三、問題二：合併兩個有序鏈表

輸入：head1、head2 均為遞增有序鏈表
輸出：合併後的有序鏈表（保留所有節點，含重複值）

方法一：非遞歸（迭代法）——推薦用於生產環境

Linknode* mergeIterative(Linknode* head1, Linknode* head2) {
    // 1. 邊界處理
    if (head1 == NULL) return head2;
    if (head2 == NULL) return head1;
    
    // 2. 確定新鏈表頭節點
    Linknode *newHead, *cur;
    Linknode *p1 = head1, *p2 = head2;
    
    if (p1->data <= p2->data) {
        newHead = cur = p1;
        p1 = p1->next;
    } else {
        newHead = cur = p2;
        p2 = p2->next;
    }
    
    // 3. 循環合併：雙指針比較，小者接入新鏈表
    while (p1 != NULL && p2 != NULL) {
        if (p1->data <= p2->data) {
            cur->next = p1;
            p1 = p1->next;
        } else {
            cur->next = p2;
            p2 = p2->next;
        }
        cur = cur->next;
    }
    
    // 4. 接上剩餘部分
    cur->next = (p1 != NULL) ? p1 : p2;
    
    return newHead;
}

方法二：遞歸法——代碼簡潔但有棧溢出風險

Linknode* mergeRecursive(Linknode* head1, Linknode* head2) {
    // 1. 遞歸基準情況
    if (head1 == NULL) return head2;
    if (head2 == NULL) return head1;
    
    Linknode* newHead;
    
    // 2. 選擇較小頭節點，遞歸處理剩餘部分
    if (head1->data <= head2->data) {
        newHead = head1;
        newHead->next = mergeRecursive(head1->next, head2);
    } else {
        newHead = head2;
        newHead->next = mergeRecursive(head1, head2->next);
    }
    
    return newHead;
}

兩種方法對比

四、測試驗證

Linknode* createList(int n) {
    Linknode *head = NULL, *tail = NULL;
    for (int i = 0; i < n; i++) {
        Linknode* node = (Linknode*)malloc(sizeof(Linknode));
        node->data = rand() % 100;  // 隨機數據
        node->next = NULL;
        if (!head) head = tail = node;
        else { tail->next = node; tail = node; }
    }
    // 實際測試時需先排序，此處略過
    return head;
}

int main() {
    // 測試倒數第K個節點
    Linknode* list = createList(10);
    findLastKnode(list, 3);
    
    // 測試合併（假設已排序）
    Linknode* l1 = createList(5);
    Linknode* l2 = createList(5);
    Linknode* merged = mergeIterative(l1, l2);  // 或 mergeRecursive
    
    return 0;
}

五、總結與延伸

1. 雙指針技巧：倒數第K問題是「快慢指針」模式的經典應用，可延伸至環檢測、中點查找等
2. 合併邏輯復用：歸併排序的 merge 階段即基於此邏輯
3. 遞歸轉迭代：理解遞歸版本有助於掌握問題的分治本質，生產環境優先選迭代版

這兩道題目涵蓋了鏈表操作的核心技巧：指標操作、邊界處理、遞歸與迭代轉換，是面試與實戰中的高頻考點。