複雜鏈表深度複製：O(1) 空間三步法完整解析

題目

複製複雜鏈表：每節點除 next 外還有 sibling 指向任意節點或 null。要求時間 O(n)、額外空間 O(1)（不含輸出）。

三步法核心思路

1. 複製節點插入原鏈表：原節點 N 後插入複製節點 N'，N'.next = N.next，N.next = N'。
2. 設置 sibling 指針：若 N.sibling = S，則 N'.sibling = S.next（即 S'）。
3. 拆分鏈表：將交織的鏈表拆分為原鏈表與複製鏈表。

完整 C++ 代碼

struct ComplexListNode {
    int val;
    ComplexListNode *next, *sibling;
    ComplexListNode(int v) : val(v), next(nullptr), sibling(nullptr) {}
};

ComplexListNode* clone(ComplexListNode* head) {
    if (!head) return nullptr;
    // 1. 複製並插入
    for (ComplexListNode* p = head; p; p = p->next->next) {
        ComplexListNode* copy = new ComplexListNode(p->val);
        copy->next = p->next;
        p->next = copy;
    }
    // 2. 設置 sibling
    for (ComplexListNode* p = head; p; p = p->next->next) {
        if (p->sibling) p->next->sibling = p->sibling->next;
    }
    // 3. 拆分
    ComplexListNode* copyHead = head->next;
    for (ComplexListNode* p = head; p; p = p->next) {
        ComplexListNode* copy = p->next;
        p->next = copy->next;
        copy->next = copy->next ? copy->next->next : nullptr;
    }
    return copyHead;
}

關鍵點與變體

• 拆分時注意 copy->next 可能為 null。
• 若允許 O(n) 空間，哈希表 原節點 → 複製節點 更直觀：兩遍遍歷，第一遍建節點與映射，第二遍連 next 和 sibling。
• 本題源自《劍指 Offer》面試題 35。