[数据结构与算法]剑指offer35.复杂链表的复制

为什么不可以直接将每个节点复制下来？

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(head == nullptr) return nullptr;
        //如果链表为空，直接返回就好
        Node* cur = head;
        // 1. 复制各节点，并构建拼接链表
        while(cur != nullptr) {
            Node* tmp = new Node(cur->val);
            //动态内存分配一个新的链表节点
            tmp->next = cur->next;
            //记下原来下一个节点的位置
            cur->next = tmp;
            //将新的同样的值的节点接在原来的链表节点之后
            cur = tmp->next;
            //移动到原来的下一个节点
        }
        // 2. 构建各新节点的 random 指向
        cur = head;
        while(cur != nullptr) {
            if(cur->random != nullptr)
                cur->next->random = cur->random->next;
                //cur->next是复制后的节点，复制后的节点的随机指针，指向原来的随机指针指向的下一个，因为所有复制后的节点都在原来节点的下一个。
            cur = cur->next->next;
            //移动到下一个原来的节点
        }
        // 3. 拆分两链表
        cur = head->next;
        Node* pre = head, *res = head->next;//标记新的节点的开头
        while(cur->next != nullptr) {
            pre->next = pre->next->next;
            cur->next = cur->next->next;
            pre = pre->next;
            cur = cur->next;
        }
        pre->next = nullptr; // 单独处理原链表尾节点
        return res;      // 返回新链表头节点
    }
};

作者：jyd
链接：https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof/solution/jian-zhi-offer-35-fu-za-lian-biao-de-fu-zhi-ha-xi-/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。