【C++】LeetCode：LCR 154. 复杂链表的复制

题干：

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

官方示例图：

题解：哈希表

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/
class Solution {
public:
    Node* copyRandomList(Node* head) {
        
        Node *cur  = head;
        unordered_map<Node *, Node *>map;

        while(cur!=nullptr){
            map[cur]=new Node(cur->val);
            cur = cur->next;
        }
        cur = head;
        while(cur!=nullptr){
            map[cur]->next = map[cur->next];
            map[cur]->random = map[cur->random];
            cur = cur->next;
        }
        return map[head];
    }
};

解析：

1. 第一次遍历：只创建新节点，并建立原节点到新节点的映射关系（即哈希表）。这一步确保了每个原节点都有一个对应的新节点，但此时还不处理 next 和 random 指针。
2. 第二次遍历：利用第一次遍历建立的映射关系，设置新链表中每个节点的 next 和 random 指针。

详细步骤

1. 检查空链表：

   • 如果输入的 head 是 nullptr，则直接返回 nullptr。这是为了处理空链表的情况。

2. 初始化变量和哈希表：

   • Node* cur = head;：用 cur 来遍历原链表。
   • unordered_map<Node*, Node*> map;：声明一个哈希表，用于存储原节点到新节点的映射关系。

3. 第一次遍历：

   • while(cur != nullptr)：遍历原链表中的每一个节点。
     • map[cur] = new Node(cur->val);：为每个原节点创建一个新的节点，并将原节点和新节点的映射存入哈希表中。
     • cur = cur->next;：移动到下一个节点继续操作。

4. 重置遍历指针：

   • cur = head;：将 cur 重新指向链表的头节点，准备进行第二次遍历。

5. 第二次遍历：

   • while(cur != nullptr)：再次遍历原链表。
     • map[cur]->next = map[cur->next];：根据哈希表找到当前节点对应的新的 next 节点，并建立连接。注意这里 cur->next 可能是 nullptr，所以 map[cur->next] 也可能是 nullptr。
     • map[cur]->random = map[cur->random];：同样地，根据哈希表找到当前节点对应的新的 random 节点，并建立连接。这里 cur->random 也可能为 nullptr。
     • cur = cur->next;：移动到下一个节点继续操作。

6. 返回新链表的头节点：

   • return map[head];：最后返回新链表的头节点，它是通过哈希表从原链表的头节点映射得到的。

关键点

• 哈希表的作用：哈希表在这里起到了至关重要的作用，它保存了原节点和新节点之间的映射关系，使得在第二次遍历时可以快速找到对应的节点，从而正确设置 next 和 random 指针。
• 两次遍历的原因：第一次遍历是为了确保所有节点都被复制并且建立了映射关系；第二次遍历则是为了根据这些映射关系正确设置新链表中每个节点的 next 和 random 指针。如果只进行一次遍历，我们无法在创建节点的同时正确设置 random 指针，因为 random 指针可能指向尚未创建的节点。

复杂度分析

• 时间复杂度：O(n)，其中 n 是链表中节点的数量。每个节点都访问了两次，一次用于创建新节点并建立映射，另一次用于设置 next 和 random 指针。
• 空间复杂度：O(n)，因为我们为每个节点都创建了一个新的节点，并且使用了额外的哈希表来存储映射关系。