C語言複雜鏈表深度複製：O(1) 空間三步法完美解法

問題定義

複雜鏈表節點包含三個指標：`_next`（下一節點）、`_random`（任意節點/NULL）。要求**深度複製**整個鏈表，新舊節點記憶體完全獨立，且 `_random` 指向對應的新節點。

節點結構

typedef struct ComplexNode {
    int _data;
    struct ComplexNode *_next;
    struct ComplexNode *_random;
} ComplexNode, *pComplexNode;

O(1) 空間三步法核心思想

1. 交織複製：在每個原節點後插入其複製節點。
   `A -> B -> C` 變為 `A -> A' -> B -> B' -> C -> C'`
2. 設定 random：利用 `原節點->_random->_next` 即為複製節點的 random 目標。
3. 拆分鏈表：將交織鏈表拆分為原鏈表與新鏈表。

完整實作程式碼

#include 
#include 

// 複製複雜鏈表
void CopyComplexList(pComplexNode head, pComplexNode *newHead) {
    if (!head) { *newHead = NULL; return; }

    // 步驟 1: 交織複製節點
    pComplexNode cur = head;
    while (cur) {
        pComplexNode copy = malloc(sizeof(ComplexNode));
        copy->_data = cur->_data;
        copy->_next = cur->_next;
        copy->_random = NULL;
        cur->_next = copy;
        cur = copy->_next;
    }

    // 步驟 2: 設定 random 指標
    cur = head;
    while (cur) {
        pComplexNode copy = cur->_next;
        if (cur->_random)
            copy->_random = cur->_random->_next; // 關鍵！
        cur = copy->_next;
    }

    // 步驟 3: 拆分兩個鏈表
    cur = head;
    *newHead = head->_next;
    while (cur) {
        pComplexNode copy = cur->_next;
        cur->_next = copy->_next; // 恢復原鏈表
        if (copy->_next)
            copy->_next = copy->_next->_next; // 串聯新鏈表
        cur = cur->_next;
    }
}

// 輔助：建立測試鏈表
pComplexNode build_test_list() {
    pComplexNode n1 = malloc(sizeof(ComplexNode)); n1->_data = 1;
    pComplexNode n2 = malloc(sizeof(ComplexNode)); n2->_data = 2;
    pComplexNode n3 = malloc(sizeof(ComplexNode)); n3->_data = 3;
    pComplexNode n4 = malloc(sizeof(ComplexNode)); n4->_data = 4;
    n1->_next = n2; n2->_next = n3; n3->_next = n4; n4->_next = NULL;
    n1->_random = n3; n2->_random = n4; n3->_random = n2; n4->_random = n1;
    return n1;
}

void print_list(pComplexNode head) {
    while (head) {
        printf("Node %d: random -> %s\n", head->_data,
               head->_random ? "Node %d" : "NULL", head->_random ? head->_random->_data : 0);
        head = head->_next;
    }
}

int main() {
    pComplexNode head = build_test_list();
    pComplexNode newHead = NULL;
    CopyComplexList(head, &newHead);
    printf("Original:\n"); print_list(head);
    printf("Copy:\n"); print_list(newHead);
    // 驗證記憶體獨立性
    return 0;
}

關鍵細節圖解

步驟1 交織:
原:  1  ->  2  ->  3  ->  4
新:  1' ->  2' ->  3' ->  4'
合:  1 -> 1' -> 2 -> 2' -> 3 -> 3' -> 4 -> 4'

步驟2 設定 random:
原 1.random = 3  =>  1'.random = 3->_next = 3'
原 2.random = 4  =>  2'.random = 4->_next = 4'
...

步驟3 拆分:
原鏈表恢復: 1 -> 2 -> 3 -> 4
新鏈表形成: 1' -> 2' -> 3' -> 4'

替代方案比較

常見錯誤

1. 拆分時未處理 `copy->_next` 為 `NULL` 的邊界（最後一個複製節點）。
2. 忘記恢復原鏈表 `_next` 指標，導致原表損壞。
3. `malloc` 失敗未檢查（教學碼常省略，生產碼必須處理）。

總結

複雜鏈表深度複製是經典面試硬題。**三步法（交織→設random→拆分）**以 O(1) 額外空間、O(n) 時間完美解決，展現了「利用原結構暫存資訊」的精妙思維。務必熟練手寫三個 while 迴圈，並能畫出記憶體圖解釋每一步指標變化。