面试题35：复杂链表的复制

把克隆节点交织到原节点后，用紧邻关系常数时间定位随机指针目标，最后同步恢复原链并拆出独立深拷贝。

学习目标

  • 能说出三阶段法：复制节点插入原后、复制随机指针、拆分两链
  • 能解释"紧邻关系"如何常数时间定位随机指针目标
  • 能区分深拷贝与浅拷贝并验证克隆独立性

从“复制值以后，sibling该指向谁”开始

先预测：原节点A的sibling指向原节点C。新建A′后，若直接令A′.sibling等于A.sibling，它会指回原C，克隆链仍依赖原链，并不是真正复制。目标必须是与原C对应的新节点C′。

“复杂链表的复制”中每个节点有m_pNext和m_pSibling，后者也常叫random。值和next只能确定主链，随机指针可能向前、向后、指自己、为空或形成环。核心任务是建立。

哈希表可以显式保存原地址到克隆地址；作者则把映射编码进临时链表结构，让满足原节点.next就是它的克隆。

阶段1：复制节点插入原节点后面1original1′clone2original2′clone3original3′clone原1.sibling → 原3，因此克隆1′.sibling → 原3.next = 克隆3′局部公式：clone(original) = original.next
交织后无需哈希表：任意原节点的克隆就是它紧邻的next，随机目标的克隆也可同样定位。

阶段一：复制节点插入原节点后面

遍历原next链。对每个pNode新建pCloned，复制value；令pCloned.next等于原pNode.next，再令pNode.next等于pCloned。随后从pCloned.next跳到下一个原节点，避免把刚插入的克隆再次复制。

原A→原B→原C变为原A→克隆A′→原B→克隆B′→原C→克隆C′。原节点的相对顺序没变，克隆节点也按相同顺序出现，只是两条链暂时交错。

“复制节点插入原节点后面”带来：clone(x)等于x.next。阶段二和阶段三都依赖它，不能提前恢复next。

阶段二：复制

遍历每个原节点pNode，克隆就是pNode.next。若原sibling为空，克隆保持空；否则原目标s的克隆是s.next，因此赋值pCloned.sibling等于pNode.sibling.next。

原关系克隆赋值结论
原节点sibling为空克隆sibling保持nullptr无目标
原A.sibling=原C克隆A′.sibling=原C.next原C.next恰为克隆C′
原B.sibling=原B克隆B′.sibling=原B.next得到克隆B′自指
原B与原D互指B′指D′，D′指B′sibling环被同构复制
sibling指向链外节点公式不再成立违反作者输入契约
随机指针可指向前方、后方、自身或形成环；只要目标属于next主链，紧邻映射都有效。

这一步“复制随机指针”不沿sibling遍历，只读取一次目标的next，因此sibling形成环也不会无限循环。Test3中原2与原4互指，克隆2′和4′会自然互指；Test2与Test4的自指也自然变为克隆自指。

算法隐含约束：每个非空sibling必须指向同一条next主链中的某个原节点，因为只有这些节点后面插入了克隆。若指向链外对象，目标.next不是其克隆，公式失效。一般对象图复制应使用哈希映射。

阶段三：拆分两个链表

完成sibling后，交织结构不再需要。拆分必须同时做两件事：把每个原节点next恢复到下一个原节点；把每个克隆节点next连接到下一个克隆节点。

阶段原链next克隆链next不变量
交织前A→B→C无原链完整
交织后A→A′→B→B′→C→C′尚未独立映射可局部读取
先取克隆头A.next=A′cloneHead=A′保存返回入口
每轮恢复原nextA→B→CA′→B′→C′两条链同步前进
完成与输入地址和值关系一致全新节点与同构引用原链恢复、克隆独立
拆分不能只取奇数位；每次还要恢复原节点next，并把克隆节点next接到下一个克隆。

作者先单独处理首对，保存pClonedHead并恢复原头next。循环中令当前克隆next等于下一个原节点next，也就是下一个克隆；随后恢复该原节点next。最终原链与调用前相同，返回克隆头。

不是只移动返回指针。如果忘记恢复原next，调用方原链仍夹着克隆；如果忘记连接克隆next，返回链只有头或仍穿过原节点。

忠实还原作者三函数实现

作者Clone无条件依次调用三个阶段；空头时前两阶段循环不执行，ReconnectNodes返回nullptr。

struct ComplexListNode {
    int m_nValue;
    ComplexListNode* m_pNext;
    ComplexListNode* m_pSibling;
};
 
void CloneNodes(ComplexListNode* pHead) {
    ComplexListNode* pNode = pHead;
    while (pNode != nullptr) {
        auto* pCloned = new ComplexListNode();
        pCloned->m_nValue = pNode->m_nValue;
        pCloned->m_pNext = pNode->m_pNext;
        pCloned->m_pSibling = nullptr;
        pNode->m_pNext = pCloned;
        pNode = pCloned->m_pNext;
    }
}
 
void ConnectSiblingNodes(ComplexListNode* pHead) {
    ComplexListNode* pNode = pHead;
    while (pNode != nullptr) {
        ComplexListNode* pCloned = pNode->m_pNext;
        if (pNode->m_pSibling != nullptr) {
            pCloned->m_pSibling =
                pNode->m_pSibling->m_pNext;
        }
        pNode = pCloned->m_pNext;
    }
}
 
ComplexListNode* ReconnectNodes(ComplexListNode* pHead) {
    ComplexListNode* pNode = pHead;
    ComplexListNode* pClonedHead = nullptr;
    ComplexListNode* pClonedNode = nullptr;
 
    if (pNode != nullptr) {
        pClonedHead = pClonedNode = pNode->m_pNext;
        pNode->m_pNext = pClonedNode->m_pNext;
        pNode = pNode->m_pNext;
    }
 
    while (pNode != nullptr) {
        pClonedNode->m_pNext = pNode->m_pNext;
        pClonedNode = pClonedNode->m_pNext;
        pNode->m_pNext = pClonedNode->m_pNext;
        pNode = pNode->m_pNext;
    }
    return pClonedHead;
}
 
ComplexListNode* Clone(ComplexListNode* pHead) {
    CloneNodes(pHead);
    ConnectSiblingNodes(pHead);
    return ReconnectNodes(pHead);
}

三个遍历都沿原节点推进：交织后每次跨过克隆到下一个原节点；拆链后原与克隆指针同步前进。任何阶段若把pNode简单设为pNode.next，就会落到克隆节点并破坏奇偶角色。

应验证什么

不只是打印值相同。对第i个原节点和克隆节点，应满足：地址不同、值相同；next为空状态相同且克隆next对应原next；sibling为空状态相同且克隆sibling对应原sibling。

还要验证原链被完全恢复。克隆后再次遍历原next应得到相同地址序列；原节点next和sibling都应与调用前快照一致。修改克隆节点值或sibling不应影响原节点，反之亦然。

若节点值重复，不能按value匹配对应关系；必须按next位置或测试前建立的地址索引。Test输出两条链供人工观察，但没有自动证明地址独立，也没有释放原链和克隆链，生产测试应补上。

哈希映射是更稳妥的替代

交织法O(1)辅助空间，但会临时修改输入，不适合只读、并发共享或链外sibling。哈希法第一遍为每个原节点创建克隆并建立map，第二遍按map连接next与sibling，原链始终不变。

#include <memory>
#include <unordered_map>
#include <vector>
 
struct Node {
    int value;
    Node* next = nullptr;
    Node* sibling = nullptr;
};
 
Node* cloneWithMap(const Node* head) {
    if (head == nullptr) return nullptr;
 
    std::unordered_map<const Node*, Node*> cloneOf;
    std::vector<std::unique_ptr<Node>> owned;
 
    for (const Node* node = head;
         node != nullptr; node = node->next) {
        owned.push_back(std::make_unique<Node>());
        owned.back()->value = node->value;
        cloneOf.emplace(node, owned.back().get());
    }
 
    for (const Node* node = head;
         node != nullptr; node = node->next) {
        Node* copy = cloneOf.at(node);
        copy->next =
            node->next == nullptr ? nullptr : cloneOf.at(node->next);
        copy->sibling =
            node->sibling == nullptr
                ? nullptr
                : cloneOf.at(node->sibling);
    }
 
    for (auto& node : owned) node.release();
    return cloneOf.at(head);
}

unique_ptr暂时拥有新节点；分配或map操作抛异常时已创建节点自动释放。全部关系连接成功后才release所有权。真实库更适合返回拥有整条链的RAII类型，而不是裸头指针；这里保持与题目接口接近。

哈希法时间O(n)、映射辅助空间O(n)。交织法也是O(n)时间，辅助指针O(1)，但新建的n个克隆节点是必要输出，不计入“额外工作空间”并不代表总分配O(1)。

临时修改与异常安全

作者CloneNodes每创建一个克隆就修改原next。若第k次new抛出，前k减1个节点已交织，原链处于半转换状态，克隆也无人释放；函数没有回滚，异常安全不足。

可预先分配全部节点再交织，或用哈希RAII方案。若坚持O(1)辅助空间与裸指针，可捕获异常并从头识别已交织前缀、恢复原next、删除克隆，但边界复杂，且异常处理本身必须不再抛。

遍历期间其他线程会看到A→A′→B的临时结构，可能把克隆当业务节点；必须独占访问或使用不可变哈希法。即使单线程，回调、日志钩子或析构器也不应在交织窗口遍历原链。

作者五组测试覆盖什么

Test1主链1到5，sibling为1→3、2→5、4→2，其余空，覆盖向前与向后跨节点。Test2为2→5、3→自身、4→2，覆盖自指。Test3让2→4且4→2，形成sibling环。

Test4只有节点1，next为空、sibling指向自己；克隆后1′必须指向自身而非原1。Test5传nullptr，返回nullptr。源码总计五组。

#include <cassert>
#include <unordered_map>
#include <vector>
 
void assertDeepClone(const Node* original, const Node* copy) {
    std::vector<const Node*> oldNodes;
    std::vector<const Node*> newNodes;
    for (auto* p = original; p != nullptr; p = p->next)
        oldNodes.push_back(p);
    for (auto* p = copy; p != nullptr; p = p->next)
        newNodes.push_back(p);
 
    assert(oldNodes.size() == newNodes.size());
    std::unordered_map<const Node*, std::size_t> oldIndex;
    for (std::size_t i = 0; i < oldNodes.size(); ++i) {
        oldIndex[oldNodes[i]] = i;
        assert(oldNodes[i] != newNodes[i]);
        assert(oldNodes[i]->value == newNodes[i]->value);
    }
    for (std::size_t i = 0; i < oldNodes.size(); ++i) {
        const Node* sibling = oldNodes[i]->sibling;
        if (sibling == nullptr) {
            assert(newNodes[i]->sibling == nullptr);
        } else {
            assert(newNodes[i]->sibling ==
                   newNodes[oldIndex.at(sibling)]);
        }
    }
}

测试前还应保存原节点next地址序列，调用后确认完全恢复；分别销毁两条链并使用内存检测工具验证无泄漏、无双重释放。对作者Test1到Test4，克隆后修改任一新节点值，原值必须保持不变。

正确性证明

阶段一结束后，对每个原节点x，x.next是唯一克隆x′，而x′.next是原来的下一个原节点；此为交织不变量。阶段二读取原x.sibling=s，按不变量s.next=s′，因此赋给x′.sibling得到正确克隆关系，空指针也保持空。

阶段三沿交织序列恢复x.next为x′.next，并令x′.next指向下一原节点的next，也就是下一克隆。归纳每轮后，已处理前缀的原链与克隆链都正确独立，未处理后缀仍交织可定位。

结束时所有原next恢复，所有克隆next按原顺序连接；值在创建时复制，sibling在阶段二同构连接，所以返回结构是独立深拷贝。

输入契约与复杂度

next必须形成有限无环单链。next成环会让三个while无限循环；共享next前驱则不再是链。sibling可成环，但必须为空或指向同一主链节点。

每阶段扫描O(n)，总时间O(n)。交织法除克隆输出外只用常数个指针，辅助空间O(1)；递归未使用，调用栈O(1)。哈希法辅助空间O(n)，但不修改原链且更易获得异常安全。

若克隆由垃圾回收语言实现，交织期间原与克隆互相可达，不会被回收；拆分后仍需确保返回头持有全部新节点。弱引用sibling、所有权sibling或外部引用会改变复制语义，不能只照搬裸指针模型。

本章练习

练习

问题 1： 三阶段法的三个阶段各做什么？

问题 2： 为什么"紧邻关系"能 O(1) 定位随机指针目标？

问题 3： 深拷贝应验证哪些性质？

概念说明

本章核心概念：拆分两个链表。理解这些概念是掌握解题方法的关键，具体实现与边界条件请参考上文对应小节。

本章回顾

  1. 复杂链表复制要保持值、next和sibling拓扑同构且地址独立。
  2. 阶段一把每个克隆节点插在对应原节点后，建立局部映射。
  3. 克隆sibling等于原sibling.next，前提是目标属于同一主链。
  4. sibling自指或成环不会导致额外遍历，仍可常数时间映射。
  5. 拆链同时恢复原next并连接克隆next，最终得到两条独立链。
  6. 交织法O(n)时间、O(1)辅助空间，但会临时修改输入。
  7. 作者版本在new中途失败时缺少回滚；哈希加RAII更稳健。
  8. 五组官方测试覆盖跨引用、自指、sibling环、单点与空链。

名词解释

名词解释

本章出现的专业名词，用大白话再讲一遍。

节点映射
原节点到其克隆节点的对应关系，三阶段法用"紧邻"隐式建立。
随机指针
指向链中任意节点的额外指针（sibling），可能成环。
深拷贝
复制全部结构，克隆链不共享原节点，完全独立。
复习本章（5 题）

讨论

评论区加载中…