【算法】 随机链表的复制难度：中等 题目： 给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random

难度：中等

题目：

给你一个长度为 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：

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

示例 2：

输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]

示例 3：

输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]

提示：

• 0 <= n <= 1000
• -104 <= Node.val <= 104
• Node.random 为 null 或指向链表中的节点。

解题思路：

深拷贝意味着我们需要创建一个新的链表，其中的节点与原始链表的节点具有相同的值，但是 next 和 random 指针指向的都是新链表中的新节点。我们可以通过以下三个步骤来解决这个问题：

1. 复制节点并插入到原节点后面：遍历原链表，对于每一个节点，在其后面插入一个与其值相同的节点，形成一个交织链表。这样做的好处是新节点紧挨着原节点，方便后续步骤中 random 指针的复制。
2. 复制 random 指针：再次遍历交织链表，为每个新节点设置正确的 random 指针。由于新节点就在原节点后面，我们可以很容易地找到原节点的 random 指针所指向的节点的下一个节点，即新节点的 random 指针应该指向的节点。
3. 拆分链表：最后，将交织链表拆分成两个独立的链表。原链表保持不变，新链表由原链表中每个节点后面插入的节点构成。

JavaScript代码实现：

/**
 * Definition for a Node.
 * function Node(val, next, random) {
 *    this.val = val;
 *    this.next = next;
 *    this.random = random;
 * };
 */

/**
 * @param {Node} head
 * @return {Node}
 */
var copyRandomList = function(head) {
    if (!head) return null;

    // Step 1: Copy nodes and insert them next to original nodes
    let current = head;
    while (current) {
        const newNode = new Node(current.val);
        newNode.next = current.next;
        current.next = newNode;
        current = newNode.next;
    }

    // Step 2: Adjust random pointers for copied nodes
    current = head;
    while (current) {
        if (current.random) {
            current.next.random = current.random.next;
        }
        current = current.next.next;
    }

    // Step 3: Separate the copied list from the original list
    current = head;
    let copiedHead = head.next;
    let copiedCurrent = copiedHead;
    while (current) {
        current.next = copiedCurrent.next;
        current = current.next;
        if (current) {
            copiedCurrent.next = current.next;
            copiedCurrent = copiedCurrent.next;
        }
    }

    return copiedHead;
};