本文主要是介绍算法题解记录27+++随机链表的复制（百日筑基），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一、题目描述：
题目难度：中等
给你一个长度为 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-10^4 <= Node.val <= 10^4Node.random为null或指向链表中的节点。
二、解题准备
1.了解题意：
题目要求拷贝链表，需要注意的是，本题链表的定义和普通链表不同，本题链表的节点，除了val域和next域，还有一个random域，随机指向本链表的某一节点【但是这链表肯定不是环形链表】
深度拷贝，要求复制出一个一模一样的链表，这种链表，除了val域一样，next域指向新节点外，random域指向的节点，不能是原先链表的节点。
用3元式表示一个节点【val，next，random】，其中，@x表示指向第x个节点，这个x从0开始。
举个例子，我们有一个链表【1，@1，@NULL】，【4，@2，@3】，【10，@3，@0】，【7，@NULL，@NULL】
这个链表类似于下图【不懂绘图，勉强看吧】
我们需要的新链表，要与这个一模一样，但是是下图这样的：
至此你应该理解了题意。
2.基本操作：
本题涉及链表的创建和增加。
3.基础原理：
对于链表题目，要记住最基础的一个方法（如何遍历链表）：
如果是使用迭代while，那么，基础的迭代语法就是：
Node temp = head; // 防止遍历结束后，丢失读取链表的方法
while(temp!=null){print(temp.val); // 伪代码，访问temp的数据temp = temp.next;
}
// 结束条件：最终temp指向第一个null“节点”三、解题思路
首先考虑，如果去除random域，那么如何复制一份链表？
1.简化思路：最基本的链表拷贝方法
拷贝一个链表，其实是拷贝链表的val域，以及链表节点之间的相互关系。
比如上面说的例子【1，4，10，7】。我们知道链表间的关系就是1指向4，4指向10，10指向7。
由于链表的next域自带这种联系方式，所以拷贝的时候，不必把相互关系存储起来，而是在遍历时，一边拷贝即可。
也就是说，我们首先创建一个对象res，指向head（或者用哑节点也行，无所谓）
然后，遍历原链表，同时不断创建新结点。
代码如下：
Node res = new Node(head.val); // 指向头节点temp = head.next; // 如果指向head，那么while中会拷贝len次，而res已经拷贝一次real = res; // 指向头节点，避免丢失res// 一直迭代到temp指向第一个null节点。while(temp!=null){// 为什么用next？因为如果用real本身，会丢失联系。// 解释：real原先是一个null节点，你new之后，前面的联系就断了real.next = new Node(temp.val);temp = temp.next;real = real.next;}return res; // res就是我们要的答案得到拷贝基础链表的方法后，开始考虑本题的random域链表。
我们首先要确定一件事：
拷贝一个数据结构，就是拷贝元素值，以及元素之间的相互关系。
如果进行一遍“简化思路”，那么，除了random域的元素关系，其它的元素关系都被拷贝了。
所以，只需要考虑如何把random域的元素关系拷贝即可。
2.思路：存储random域的元素关系
如题，由于random是随机指向某个节点的，而链表不支持随机访问，也不能知道某个节点，在整个链表里，排在第几个元素。
所以，我们需要用一个结构，将链表节点之间联系起来。
比较简单地，自定义一个Class，有一个Node和一个int属性，头节点head是0，之后的按顺序排序。
这里有一个问题：我们可以知道原链表的节点关系，但是无法映射到新链表中。
解释：新链表是新对象，占用新内存，所以与原节点不能用“==”判同。
因此，这个Class类，需要有两个Node、一个int属性，与上述类似，不过此时，两个Node，一个存储原链表的节点，另一个存储现在链表的节点。【在后续应用中，甚至不用int属性】
此时，拷贝random域有方法了。解释：
我们在浅度拷贝（即没考虑random域）时，将Class类填满。
然后进行第二次遍历，这次遍历，从head开始，把原链表的每一个节点的random域找到，然后在Class中对应的新Node，即可深度拷贝。
新问题：这种Class结构，需要花费很多资源，遍历起来也比较麻烦。
解决方案：用HashMap。
四、解题难点分析
无。
五、代码【HashMap】
class Solution {public Node copyRandomList(Node head) {// 空节点直接返回if(head == null){return null;}// 存储新、旧节点间关系Map<Node, Node> maps = new HashMap<>();Node temp = head.next;Node res, real;res = new Node(head.val);res.next = head.next;// 浅度拷贝real = res;maps.put(head, res);while(temp!=null){real.next = new Node(temp.val);maps.put(temp, real.next);temp = temp.next;real = real.next;}// 拷贝random域temp = head;real = res;while(temp!=null){if(temp.random != null){// 非空，则通过原链表的random域，映射到新链表的random域real.random = maps.get(temp.random);}temp = temp.next;real = real.next;}return res;}
}已经很久没更新百日筑基的内容了，一方面是这段时间忙于实训，需要重新学习、复习很多基础的框架知识，另一方面，算法题的刷题出现了瓶颈，对于回溯算法、贪心算法和图论，我已经觉得有点力不从心，虽然这些题目不难，但是由于自身知识储备不足，学起来比较吃力。
不过好在，我已经大概刷了60余题，写百日筑基系列的基础，至少也到了下一个月，所以还是不担心缺少内容创作。这段文字写得很乱，也不知道有没有人在看这个系列，不过我会坚持下去的，积累就是人生漫漫长路的解决方案啊。
以上内容即我想分享的关于力扣热题27的一些知识。
我是蚊子码农，如有补充，欢迎在评论区留言。个人也是初学者，知识体系可能没有那么完善，希望各位多多指正，谢谢大家。
这篇关于算法题解记录27+++随机链表的复制（百日筑基）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
