经典OJ题：随机链表的复制

目录

题目：

本题的解图关键在于画图与看图！ 

思路分析：

方法一：暴力求解法。

方法二：插入法

方法解析：

 步骤一、插入

步骤二、 处理每一个copy的randdom指针⭐————重点

步骤三、拆卸节点

代码演示：

---

题目：

给你一个长度为 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 作为传入参数。

• 题目大意：复制一个单链表，并返回一个单链表，需要复制的单链表，它的节点结构是有一个next指针和一个random指针，next指针和普通单链表的next指针一样，但是random指针是随机指向链表内部的任意节点，或者指向NULL。
• 现在我们要完美的复制一个这样的链表，并返回它。

题源：138. 随机链表的复制 - 力扣（LeetCode） 

本题的解图关键在于画图与看图！ 

思路分析：

对于本题的关键是random指针的复制。

如何将每一个节点的random完完全全的，这是我们需要思考的问题，为此我们分为两种方法。

方法一：暴力求解法。

首先，将原链表A 完整的复制下来，当然，只是复制指针next和指针的数据。

而后，设立一个指针copy ，专门的对复制下来的链表B 进行遍历。

之后，再设置一个指针rand ，专门对原链表A进行遍历，并且对链表进行计数。

最后开始遍历，因为链表A和链表B的元素一样，所以我们再使用copy对链表B的random指向的时候，可以先使用指针rand，寻找相对因节点的rand指针指向的位置，并计数，然后将计数给指针copy，让其进行遍历。

而对于寻找相应节点的rand指针指向的位置是看节点中的数值是否一样。

缺点：如果使用了最坏的结果，所有random的指向都是尾节点位置，那么遍历之后，时间复杂度抵达了最高——O（N^2）

且，我们寻找对于节点的random指向是通过节点内的数值（元素），所以如果元素都一样，那就很难分别random要找的是那一个

方法二：插入法

我们再原链表的每一个节点后插入一个新的节点，通过节点和节点之间的联系完成random的指向复制操作，最后将每一个插入的新节点从原链表上拆除并重新组装在一起，返回最后的链表。

 

 优点：这种方法解决了上面暴力解法的效率问题，上面的暴力解法因为拷贝的链表和原链表没有联系，所以需要遍历操作。

而这种方法使得拷贝的节点处在了原节点的后面，使得拷贝节点的一切数值和指针指针都可以模仿原节点操作，也就说数值可以复制，而随机指针可以变成源节点的随机指针的next。

方法解析：

 步骤一、插入

再遍历中进行空间的开辟，并且利用遍历形成局部变量，方便之后的操作。

copy的next指向cur的next ， 然后cur的next指向copy ，之后cur等于copy的next

这一步创建临时的局部变量copy空间，利用遍历将每一次遍历中创建的copy插入再原链表上。

步骤二、 处理每一个copy的randdom指针⭐

将上一步中的cur返回头节点，随后设立临时的局部指针copy 指向复制节点。

再对random进行复制之前，需要为random指向NULL的节点进行单独处理。

之后，将cur->random->next赋值与copy->random

再复制完毕后，将cur移动道copy->next的位置，也就是原链表的节点位置,而copy直接再一开始的位置设置为cur->next的位置上作为临时变量。

步骤三、拆卸节点

设置一个新的指针next，用来恢复原链表和作为临时变量使用

同时定义两个指针作为拆下来组装后的头节点和尾节点，newhead和newtail

再将cur指针返回头节点进行遍历和拆卸操作，同时设立copy指向复制节点

最后当然，需要注意，设立的newhead和newtail初始值是NULL，所以先要进行赋值，赋予copy的数值后再进行遍历拆卸的尾插操作。

代码演示：

---