随机链表的复制

🍉前言

果然，力扣的简单题不一定简单，但是中等和较难的题一定很麻烦。
这道题相当综合，对于思路二，如果看完思路后能写出代码，那说明你链表掌握得相当熟练了。

🍉题目

题目链接

🍉分析

题干很长，不过总结下来就很简单的几句话：有一链表，它每个节点除了有next，还有个random指针，random指向哪里？不知道，可能是其他节点，也可能指向NULL。然后现在要你对这样一个链表进行拷贝，得到一个新链表，新链表中每个节点random的指向和原链表一模一样。

🍉思路一：暴力解法

先复制原链表，但不复制random指针，得到一个新链表。接下来要复制 random 指针，那我们得知道它指向原链表的第几个节点，假设现在要得到第一个节点 node1 的random指向哪，那就遍历链表，直到某个节点的地址和 node1->random 一样，此时该节点就是 node1 的 random，然后要记录这个节点的位置（即第几个节点），比如 node1 指向第三个节点，那你新链表第一个节点也要指向第三个节点。（这里注意不是指向原链表的第三个节点！）；如果没有找到，那就说明node1->random = NULL。
既然现在已经知道第一个节点的 random 指向第三个节点，那就遍历新链表，先遍历得到第一个节点（这里因为刚好是第一个节点，所以不用遍历，但如果不是第一个，那就要遍历了），再遍历一次找到第三个节点，然后就可以将它的地址赋给random了。

顺便来分析一下时间复杂度，最坏的情况是所有节点的 random 都指向最后一个节点，此时原链表中每个节点要找n次才能找到random指向的节点，有n个节点，所以就是n ^ 2；而新链表也是如此，所以时间复杂度就是O（N^2）。

这个解法比较复杂，代码的话你自行尝试咯。

---

🍉思路二：很绝的办法

之前的难点来源于原链表和新链表之间没有建立起联系。那么我们现在不妨这样：拷贝节点放在原链表对应的节点的后面，比如拷贝的第一个节点就插在原链表第一和第二个节点之间。最终效果如下图（黄色的表示新链表插进来的节点）

那么这样做有啥好处呢？假设原链表第一个节点的random指向第三个节点，那么新链表第一个节点的random 不就是第三个节点的下一个节点了吗？
说白了就是把“变”的化为“不变”，原先一个节点的random不是随便指吗？这就是“变”；而我现在可以用这种固定的方式去得到新链表所有节点random指针的指向，这是“不变”。

这种解法虽然很巧妙，但是写起来也是很麻烦的，不过嘛，相较于思路一，思路二的时间复杂度是O（N），这就是一个大提升。

第一步，先创建新链表的节点，然后插入，这个操作类似指定位置之后插入。

	typedef struct Node Node;Node* cur = head;//插入新链表的节点while(cur) {Node* next = cur->next;  //放循环里面其实是为了防止next为空Node* copy = (Node*)malloc(sizeof(Node));    //copy：待插入的新节点copy->val = cur->val;copy->next = next;cur->next = copy;cur = next;}

第二步，设置插入节点的random指针，（记得先将 cur 置为head）

	cur = head;while(cur) {Node* copy = cur->next;if(cur->random == NULL) {copy->random = NULL;} else {copy->random = cur->random->next;    //这一步最关键！}cur = copy->next;}

第三步，把新节点取出来，连起来就是拷贝后的链表了，记得把原链表拼接回去

	cur = head;Node* newhead = NULL,*newtail = NULL;     //创建新链表，然后刚才的新节点进行尾插while(cur) {Node* copy = cur->next;if(newhead == NULL) {newhead = newtail = copy;} else {newtail->next = copy;newtail = newtail->next;}cur = copy->next;}return newhead;

整个函数的代码：

typedef struct Node Node;
struct Node* copyRandomList(struct Node* head) {Node* cur = head;//插入新链表的节点while(cur) {Node* next = cur->next;  //放循环里面其实是为了防止next为空Node* copy = (Node*)malloc(sizeof(Node));copy->val = cur->val;copy->next = next;cur->next = copy;cur = next;}//设置新节点的random指针//先重置cur、copycur = head;  while(cur) {Node* copy = cur->next;if(cur->random == NULL) {copy->random = NULL;} else {copy->random = cur->random->next;}cur = copy->next;}//把新节点的random处理好之后，接下来要把这些新节点与原先节点分离，恢复原链表cur = head;Node* newhead = NULL,*newtail = NULL;while(cur) {Node* copy = cur->next;if(newhead == NULL) {newhead = newtail = copy;} else {newtail->next = copy;newtail = newtail->next;}cur = copy->next;}return newhead;
}