在台湾做色聊的网站犯法不百度营消 营销推广
目录
题目：
本题的解图关键在于画图与看图！
思路分析：
方法一：暴力求解法。
方法二：插入法
方法解析：
步骤一、插入
步骤二、 处理每一个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的数值后再进行遍历拆卸的尾插操作。
代码演示：
