1. 题目描述

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

构造这个链表的 深拷贝。深拷贝应该正好由 n 个全新节点组成，其中每个新节点的值都设为其对应的原节点的值。

新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。

复制链表中的指针都不应指向原链表中的节点。

示例 1：

示例 2：

2. 思路分析

~~说实话，我第一次看到这个题，都没有读懂要表达的是什么意思😂，大脑都是懵的~~

题目要求我们复制一个长度为 n 的链表，该链表除了每个节点有一个指针指向下一个节点外，还有一个 额外的指针 指向链表中的任意节点或者 null，如下图所示👇

如何去复制一个带随机指针的链表？

首先我们可以忽略 random 指针，然后对原链表的每个节点进行复制，并追加到原节点的后面，然后再去复制 random 指针。

最后我们把 原链表 和 复制链表 拆分出来，并将原链表复原。

图示过程如下：

1、在每个节点的后面加上它的复制，并将原链表和复制链表连在一起（如图所示👇）。

什么意思呢？

也就是将 拷贝节点 连接在 原节点 后面

2、 从前往后 遍历每一个原链表节点，对于有 random 指针的节点 p，我们让它的 p->next->random = p->random->next，也就是说，这样我们就完成了对原链表 random 指针的复刻（如图所示👇）。

什么意思呢？

拷贝节点的 random 在原节点 random 的后面。

p->next 指向的就是拷贝节点，p 是我们的原节点。

现在要将 原节点 的 random 拷贝到 拷贝节点 的 random 里面；

所以就是 p->next->random = p->random->next。

3、最后我们把 原链表 和 复制链表 拆分出来，并将原链表复原。

也就是说：

把 拷贝节点 拆分下来，链接到一起组成 复制链表

3. 实现过程

这题的最大难点就在于 复制随机指针，比如下图中

节点 1 的随机指针指向节点 3

节点 3 的随机指针指向节点 2

节点 2 的随机指针指向 NULL；

我们可以用三步走来搞定这个问题

🍑 拷贝

根据遍历到的原节点创建对应的新节点，每个新创建的节点是在原节点后面；

比如下图中原节点 1 不再指向原原节点 2，而是指向新节点 1

🍑 复制

这一步是最关键的一步，用来设置新链表的随机指针

上图中，我们可以观察到这么一个规律

原节点 1 的随机指针指向原节点 3，新节点 1 的随机指针指向的是原节点 3 的 next

原节点 3 的随机指针指向原节点 2，新节点 3 的随机指针指向的是原节点 2 的 next

也就是，原节点 i 的随机指针(如果有的话)，指向的是原节点 j

那么新节点 i 的随机指针，指向的是原节点 j 的 next

🍑 拆分再连接

只要将两个链表分离开，再返回新链表就可以了

4. 代码实现

接口代码

struct Node* copyRandomList(struct Node* head) {
	struct Node* cur = head;
    // 1.拷贝节点链接在原节点的后面
    while (cur) {
        struct Node* copy = (struct Node*)malloc(sizeof(struct Node));

        copy->val = cur->val; //把当原节点的val拷贝到copy节点
        copy->next = cur->next; //把原节点的next拷贝到copy节点的next
        cur->next = copy; //然后再让原节点的next指向copy节点,说明当前节点与copy节点连接起来了

        cur = cur->next->next; //开始迭代，cur->next是copy节点,copy->next->next是原链表的第二个节点
    }

    // 2.再次遍历,更新拷贝节点的random
    cur = head; // 继续让cur指向原链表的头节点
    while (cur) {
        struct Node* copy = cur->next;

        // ①如果原节点的random为空，那么copy节点的random也为空
        if (cur->random == NULL) {
            copy->random = NULL;
        }
        else { // ②如果原节点的random的不为空
            copy->random = cur->random->next; // 我的random就等于你的random的next
        }
        cur = cur->next->next; //为什么要跳两步呢？因为cur中间有个copy节点
    }

    // 3.把拷贝节点解下来，链接到一起
    cur = head;
    struct Node* copyHead = NULL, *copyTail = NULL;
    while (cur) {
        struct Node* copy = cur->next; // copy节点
        struct Node* next = copy->next; // 原链表的 原节点 的 下一个节点
        cur->next = next; // 把原链表再重新连接起来
        
        if (copyTail == NULL) { // 最开始copyTail是为空的
            copyHead = copyTail = copy; // 直接把copy给它们
        }
        else {
            copyTail->next = copy; //此时就进行尾插了
            copyTail = copyTail->next;
        }
        // 原链表的cur节点已经用完了, 让cur指向原链表的第二个节点
        cur = next;
    }
    //返回 复制链表 的头节点
    return copyHead;
}