【C++习题】22.随机链表的复制

题目：138. 随机链表的复制 - 力扣（LeetCode）

链接🔗：138. 随机链表的复制 - 力扣（LeetCode）

题目：

代码：

class Solution {
public:
    // 函数功能：深拷贝带随机指针的链表
    // 参数：原链表的头节点指针
    // 返回值：拷贝后的新链表的头节点指针
    Node* copyRandomList(Node* head) {
        // 创建map用于存储原节点到拷贝节点的映射关系
        // key: 原链表节点地址
        // value: 对应的拷贝节点地址
        map<Node*, Node*> nodeMap;
        
        // copyhead指向拷贝链表的头节点
        // copytail指向拷贝链表的尾节点
        Node* copyhead = nullptr, *copytail = nullptr;
        
        // 第一次遍历：复制节点值和next指针
        Node* cur = head;
        while(cur)
        {
            // 如果是第一个节点
            if(copytail == nullptr)
            {
                // 创建头节点
                copyhead = copytail = new Node(cur->val);
            }
            else
            {
                // 创建新节点并连接到尾部
                copytail->next = new Node(cur->val);
                copytail = copytail->next;
            }

            // 建立原节点和拷贝节点的映射关系
            nodeMap[cur] = copytail;
            
            // 继续处理下一个节点
            cur = cur->next;
        }

        // 第二次遍历：处理random指针
        cur = head;          // cur指向原链表
        Node* copy = copyhead;  // copy指向拷贝链表
        while(cur)
        {
            // 如果原节点的random为空
            if(cur->random == nullptr)
            {
                copy->random = nullptr;
            }
            else
            {
                // 通过map找到原节点random指向的节点对应的拷贝节点
                copy->random = nodeMap[cur->random];
            }
            
            // 继续处理下一个节点
            cur = cur->next;
            copy = copy->next;
        }

        return copyhead;
    }
};

算法思路解析：

1. 整体思路：
   • 分两次遍历完成深拷贝
   • 第一次遍历复制节点值和next指针，同时建立映射关系
   • 第二次遍历处理random指针
2. 具体步骤：
   • 第一次遍历：
     • 复制每个节点的值
     • 建立next连接
     • 将原节点和对应的拷贝节点存入map
   • 第二次遍历：
     • 根据原节点的random指向
     • 通过map找到对应的拷贝节点
     • 建立random连接
3. 时间复杂度：
   • O(N)，需要两次遍历链表
   • map的插入和查找操作是O(logN)
4. 空间复杂度：
   • O(N)，需要额外的map存储映射关系