一、编程题：430. 扁平化多级双向链表（双指针）
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 作为传入参数。LeetCode题目链接。
2.示例1：
输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
3.示例2：
输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]
4.示例3：
输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]
5.提示：
- 0 <= n <= 1000
- -104 <= Node.val <= 104
- Node.random 为 null 或指向链表中的节点。
二、解题思路
1. 题目分析
这里主要参考了三叶姐和官方题解提供的思路，非常感谢这些大佬。🌹 🌹 🌹
题目要求我们对一个特殊的链表进行深拷贝。这里就需要注意两点了：
- 在拷贝结束后，不能改变原链表的结构，也是说拷贝过程中可以修改，但结束之后需要还原回去；
- 在拷贝节点时，因为随机指针指向的节点可能还没创建，所以只能先建立拷贝链表，再来完成随机指针的赋值；
2. 方法1（哈希表）
思路：
- Step 1.将原节点进行复制，在采用哈希表构建原节点和新节点的映射关系；
- Step 2.对原链表进行遍历，原链表节点上的
next和random可以通过哈希表查询到对应的新节点，根据其操作给新节点的next和random指针进行赋值； - Step 3.重复2步骤，直到原链表遍历完时循环终止，并返回新链表头节点；
看不懂解释的话，直接看算法图解比较容易理解点
复杂度分析：
时间复杂度：O(n)，其中 n 是链表的长度。对于每个节点，我们至多访问其「后继节点」和「随机指针指向的节点」各一次，均摊每个点至多被访问两次。
空间复杂度：O(n)，其中 n 是链表的长度。为哈希表的空间开销。
算法图解
哈希表，红色部分代表新建立节点，灰色部分代表原链表节点；（注：本人不会做成流程动画，希望会的朋友可以私信我指点一二，说个软件名字也可以，谢谢）
3. 方法二：迭代
方法一使用哈希表就为了构建原节点和新节点和映射关系，能快速查询每个节点。但也可以不用哈希表进行构建其映射关系；
在解题过程中我们想要的是原节点和新节点的映射关系，所以将新节点复制在原节点后面，从而构建出其映射关系；
思路：
- Step 1.对原节点进行复制并将其拼接该节点后面；
- Step 2.创建好新节点后，可以发现链表中的偶数位置代表原节点，奇数位置代表了新节点（注意：这里是从0开始数起的），每个原节点的
next指针都对应着新节点； - Step 3.对链表进行遍历，通过计算
list[i].random = list[i-1].random.next构建新节点的random指针，其中i为偶数下标，list[i-1]意思是新节点前面的那个原节点； - Step 4.重复3步骤，直到原节点遍历完时循环终止，还需要对链表进行拆分再返回新链表头节点；
看不懂解释的话，直接看算法图解比较容易理解点
复杂度分析：
时间复杂度：O(n)，其中 n 是链表的长度。我们只需要遍历该链表三次。
空间复杂度：O(1)。注意返回值不计入空间复杂度。
算法图解
红色部分代表原节点，灰色部分代表新节点，蓝色部分为当前遍历的节点;（注：本人不会做成流程动画，希望会的朋友可以私信我指点一二，说个软件名字也可以，谢谢）
- 复制新节点
- 构建新节点random关系
- 拆分链表
三、代码实现
每个代码块都写了注释，方便理解，代码还可以改进；
方法一：哈希表
class Solution { public Node copyRandomList(Node head) { HashMap<Node, Node> map = new HashMap<>(); Node p = head, q; while(p != null){ q = new Node(p.val); map.put(p,q); p = p.next; } p = head; q = map.get(p); // 通过散列表特性加快查询速度 while(p != null){ q.next = map.get(p.next); q.random = map.get(p.random); q = q.next; p = p.next; } return map.get(head); } }
提交结果：
方法二：迭代
class Solution { public Node copyRandomList(Node head) { if (head == null) return head; Node first = head, temp; // 复制链表，将当前节点复制在节点后面 while(first != null){ temp = new Node(first.val); temp.next = first.next; first.next = temp; first = temp.next; } // 构建节点random关系 first = head; while(first != null){ if(first.random != null) first.next.random = first.random.next; first = first.next.next; } // 拆分链表 first = head; Node second = head.next; while(first != null){ Node temp_second = first.next; if(temp_second != null) first.next = temp_second.next; first = temp_second; } return second; } }
提交结果：
总结
以上就是今天要讲的内容，这一题还是比较容易被题意误导的，一开始我就改变了原链表的结构导致出错，后面看了各位大佬的题解就突然恍然大悟了。
感谢观看，如果有帮助到你，请给题解点个赞和收藏，让更多的人看到。🌹 🌹 🌹
也欢迎你，关注我。👍 👍 👍
原创不易，还希望各位大佬支持一下，你们的点赞、收藏和留言对我真的很重要！！！💕 💕 💕 最后，本文仍有许多不足之处，欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正！
