复制带随机指针的链表

## 1 题目

给你一个长度为 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：**
![](/media/202201/2022-01-09_2130410.7261368158867781.png)

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

**示例 2：**
![](/media/202201/2022-01-09_2131130.7809220936814016.png)

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

**示例 3：**
![](/media/202201/2022-01-09_2131310.08080883298827601.png)

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

**示例 4：**

```txt
输入：head = []
输出：[]
解释：给定的链表为空（空指针），因此返回 null。
```

**提示：**

* 0 <= n <= 1000
* -10000 <= Node.val <= 10000
* Node.random 为空（null）或指向链表中的节点。

## 2 问题解析

1. 首先，我们可以**忽略 `random` 指针**，然后**对原链表的每个节点进行复制**，**并追加到原节点的后面**，**将原链表和复制链表连在一起**：![](/media/202201/2022-01-09_2132230.7640217615405901.png)
2. 然后，**从前往后遍历每一个原链表节点**，**对于有 `random` 指针的节点 `p`**，**我们让它 `p.next.random = p.random.next`**，**这样我们就完成了对原链表 `random` 指针的复刻**：![](/media/202201/2022-01-09_2132350.36969955791205567.png)
3. 最后，**我们把原链表和复制链表拆分出来**，**并将原链表复原**：![](/media/202201/2022-01-09_2132480.08964373357277822.png)

## 3 参考代码

```java
/**
 * 138. 复制带随机指针的链表
 * @param head  链表头结点
 * @return  原链表的复制链表
 */
public Node copyRandomList(Node head) {
    //  复制每个节点，并将原链表和复制链表连在一起
    for (Node p = head; p != null; p = p.next.next) {
        Node q = new Node(p.val);
        q.next = p.next;
        p.next = q;
    }

//  复制 random 指针
    for (Node p = head; p != null; p = p.next.next) {
        if (p.random != null) {
            p.next.random = p.random.next;
        }
    }

//  拆分两个链表，并复原原链表
    Node dummy = new Node(-1), cur = dummy;
    for (Node p = head; p != null; p = p.next) {
        Node q = p.next;
        cur.next = q;
        cur = cur.next;
        p.next = q.next;
    }

//  返回原链表的复制链表
    return dummy.next;
}
```

## 参考文献

1. [138. 复制带随机指针的链表](https://leetcode-cn.com/problems/copy-list-with-random-pointer)。
2. [复制带随机指针的链表 | 图解迭代和哈希两种做法 【c++/java 版本】](https://leetcode-cn.com/problems/copy-list-with-random-pointer/solution/fu-zhi-dai-sui-ji-zhi-zhen-de-lian-biao-c2nvs)。