138. 随机链表的复制

[此处请插入：哈希表节点映射与指针构建过程示意图]

✨核心逻辑

本题采用 哈希表（HashMap）辅助法 的策略：

打破常规：因为链表中存在 random 指针，它在节点创建时不一定会指向已经存在的节点（可能指向前面的节点），所以不能在一次遍历中同时创建节点和连接 next 及 random 指针。
两次遍历：
- 第一次遍历：遍历原链表，建立一个 原节点 -> 新节点 的映射关系（此时新节点只有 val 值，next 和 random 为空）。
- 第二次遍历：再次遍历原链表。对于每一个原节点，从哈希表中取出对应的新节点，并分别将原节点的 next 指向的新节点，以及原节点的 random 指向的新节点，赋值给当前新节点对应的指针。这样就能完美解决 random 指针可能指向前面的问题。
返回结果：从哈希表中取出原头节点对应的新节点，即为复制完成的链表头。

🔥代码实现（含详细变量注释）

class Solution {
    public Node copyRandomList(Node head) {
        // 极端条件：如果原链表为空，直接返回 null
        if (head == null) {
            return null;
        }
        
        // hash：哈希表，用于存储原节点和副本节点之间的映射关系
        // 必须是 copy 节点而不是指向原来的节点
        HashMap<Node, Node> hash = new HashMap<>();
        
        // cur：维护当前遍历到的原链表节点变量
        // （之所以单独定义 cur，是为了防止直接操作 head，导致循环结束后 head 变为 null，丢失了链表的起点）
        Node cur = head;
        
        // 第一次遍历：建立原节点 -> 新节点的映射关系
        while (cur != null) {
            // 创建新节点（只包含原节点的值），并将其与原节点关联存入哈希表
            hash.put(cur, new Node(cur.val));
            cur = cur.next;
        }
        
        // 第二次遍历：通过映射关系，构建 copy 链表
        // 重新将 cur 指向原链表的头节点，开始第二次遍历
        cur = head;
        while (cur != null) {
            // copy：从哈希表中获取当前原节点对应的副本节点
            Node copy = hash.get(cur);
            
            // 利用哈希表，将当前副本节点的 next 指针，指向原节点 next 对应的副本节点
            copy.next = hash.get(cur.next);
            // 利用哈希表，将当前副本节点的 random 指针，指向原节点 random 对应的副本节点
            copy.random = hash.get(cur.random);
            
            // 继续遍历原链表的下一个节点
            cur = cur.next;
        }
        
        // 最终返回原头节点对应的副本节点（即新链表的头节点）
        return hash.get(head);
    }
}