138.随机链表的复制

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。深拷贝应该正好由 n 个全新节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

val：一个表示 Node.val 的整数。
random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。

你的代码只接受原链表的头节点 head 作为传入参数。

示例 1：

1 2	输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]] 输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

先创建所有节点的复制，再根据哈希表里面的内容重建

Solution1：哈希表

// 定义函数 copyRandomList，接收链表头节点 head 作为参数
public Node copyRandomList(Node head) {
    // 如果输入的头节点为空，直接返回 null
    if (head == null) {
        return null;
    }
    // 初始化当前节点 cur 为头节点
    Node cur = head;
    // 创建一个哈希表 map 来存储原节点与其对应的新节点的映射关系
    HashMap<Node, Node> map = new HashMap<>();
    // 遍历原链表，创建所有节点的浅拷贝，并将原节点和新创建的节点存入 map 中
    while (cur != null) {
        map.put(cur, new Node(cur.val));
        cur = cur.next;
    }
    // 再次将 cur 指向头节点，用于设置新节点的 next 和 random 指针
    cur = head;
    // 再次遍历链表，根据原链表的连接关系来更新新链表的连接关系
    while (cur != null) {
        map.get(cur).next = map.get(cur.next); // 设置新节点的 next 指针
        map.get(cur).random = map.get(cur.random); // 设置新节点的 random 指针
        cur = cur.next;
    }
    // 返回新链表的头节点，即原链表头节点对应的新节点
    return map.get(head);
  }
}

Solution2：多次迭代

class Solution {
    // 定义函数copyRandomList，接收链表头节点head作为参数
    public Node copyRandomList(Node head) {
        // 检查传入的链表头节点是否为空，若为空则返回null
        if (head == null) {
            return null;
        }
        // 第一步：复制每个节点，并将复制节点插入到原节点后面
        for (Node node = head; node != null; node = node.next.next) {
            Node nodeNew = new Node(node.val); // 创建新节点，值与原节点相同
            nodeNew.next = node.next; // 新节点的next指针指向原节点的next节点
            node.next = nodeNew; // 原节点的next指针现在指向新节点
        }
        // 第二步：设置每个新节点的random指针
        for (Node node = head; node != null; node = node.next.next) {
            Node nodeNew = node.next; // 指向新创建的复制节点
            // 设置新节点的random指针，如果原节点的random不为空，新节点的random指向原节点random的next
            nodeNew.random = (node.random != null) ? node.random.next : null;
        }
        // 第三步：将新旧链表分离，恢复原链表，提取新链表
        Node headNew = head.next; // 新链表的头节点是原链表头节点的下一个节点
        for (Node node = head; node != null; node = node.next) {
            Node nodeNew = node.next; // 指向新节点
            node.next = node.next.next; // 恢复原节点的next指针
            // 设置新节点的next指针，需要检查nodeNew.next是否为null，防止越界
            nodeNew.next = (nodeNew.next != null) ? nodeNew.next.next : null;
        }
        // 返回新链表的头节点
        return headNew;
    }
}