如何实现Linked List/SkipList深拷贝？避免原链表修改影响副本

你的代码核心问题是直接复用了原链表的节点指针，没有真正创建独立的节点内存空间。新链表和原链表的指针指向同一块堆内存，原链表的增删操作自然会同步影响新链表。

要实现完全独立的克隆，必须为新链表的每个节点分配新的内存，只复制原节点的值，不共享指针。以下是正确的实现思路和代码：

正确实现步骤 #

1. 先处理原链表为空的边界情况，避免空指针访问
2. 为新链表创建独立的头节点，复制原头节点的值
3. 遍历原链表的每个后续节点，逐个创建新节点并链接到新链表
4. 维护新链表的尾指针，避免每次遍历找尾（提升效率）

代码示例 #

假设你的链表节点定义如下：

struct SNode {
    int val;
    SNode* next;
    SNode(int x) : val(x), next(nullptr) {}
};

拷贝构造函数的正确实现：

// 假设链表类名为LinkedList，成员变量head是SNode*类型
LinkedList(const LinkedList& other) {
    // 原链表为空时，新链表也设为空
    if (other.head == nullptr) {
        head = nullptr;
        return;
    }

    // 创建新的头节点，复制原头节点的值
    head = new SNode(other.head->val);
    SNode* newTail = head; // 新链表的当前尾节点
    SNode* curr = other.head->next; // 遍历原链表的指针

    // 遍历原链表，逐个创建独立的新节点
    while (curr != nullptr) {
        newTail->next = new SNode(curr->val); // 分配新内存，复制值
        newTail = newTail->next; // 移动新链表的尾指针
        curr = curr->next; // 移动原链表的遍历指针
    }
}

关键说明 #

• 每个new SNode(...)都会在堆上分配全新的内存，新链表的节点和原链表完全独立
• 仅复制节点的数值，不共享任何指针，原链表的增删、节点值修改都不会影响新链表
• 必须处理原链表为空的边界情况，防止空指针解引用

额外注意 #

如果你的SNode包含动态分配的成员（比如字符串、数组），还需要对这些成员进行深拷贝，不能只复制指针；同时要确保链表类的析构函数能正确释放新链表的所有节点，避免内存泄漏。

内容的提问来源于stack exchange，提问作者hypebars