题目一 复制带随机指针的链表
给你一个长度为 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 有一个链表 链表的节点有三个结构组成 两个指针 一个值
2 两个指针一个指向下一个节点 一个指向一个随机节点
3 我们要拷贝一份这个链表 但是不能改变它的结构
开始想思路
还是一样 我们先看图
常规方法的遍历法时间复杂度很高，所以我们另开辟一种思路，分三个步骤
1.拷贝节点到原节点后面
2.处理拷贝节点的random，即原节点指向NULL，拷贝节点也指向NULL，否则拷贝节点指向原节点random的下一个节点
3.将拷贝节点解下来，链接成一个新链表，恢复原链表
我们按照这三个步骤一步步来分析
第一步：
struct Node*cur = head; while(cur) { struct Node*copy = (struct Node*)malloc(sizeof(struct Node)); copy->val = cur->val; struct Node*next = cur->next; cur->next = copy; copy->next = next; cur = next; }
第二步：
我们先照抄题目给我们的链表写出一个类似的链表出来 （值全部传递）
之后我们将这个单链表插入到题目给我们的链表的下一位去
这样子我们看看 如果是找随机值的话
13的随机值是指向7的
想要找到7我们只需要找到它的下一个位置就可以了！ 妙啊！
但是这里有个特殊情况哈
如果随机值是指向NULL的 我们直接赋值NULL就可以了！
也就是加一行代码的事
我们先来看看细节怎么样
cur = head; while(cur) { struct Node*copy = cur->next; if(cur->random==NULL) { copy->random = NULL; }else { copy->random = cur->random->next; } cur = cur->next->next; }
第三步：
用尾插的方法将拷贝节点尾插到新链表，再恢复原链表即可
cur = head; struct Node*copyhead = NULL,*copytail = NULL; while(cur) { struct Node*copy = cur->next; struct Node*next = copy->next; //拷贝节点尾插到新链表 if(copyhead==NULL) { copyhead =copytail = copy; }else { copytail->next = copy; copytail = copytail->next; } //恢复原链表 cur->next = next; cur = next; }
让我们来看看能通过吗
可以通过
那么这就是本题的时间复杂度0（N）的解法啦
所有代码表示如下
* struct Node { *int val; *struct Node* next; *struct Node* random; * }; */ struct Node* copyRandomList(struct Node* head) { //将拷贝节点插到原节点后面 struct Node* cur = head; while (cur) { struct Node* copy = (struct Node*)malloc(sizeof(struct Node)); copy->val = cur->val; struct Node* next = cur->next; cur->next = copy; copy->next = next; cur = next; } //拷贝节点的random指向 cur = head; while (cur) { struct Node* copy = cur->next; if (cur->random == NULL) { copy->random = NULL; } else { copy->random = cur->random->next; } cur = cur->next->next; } //将拷贝节点解下来，链接成新链表，恢复原链表 cur = head; struct Node* copyhead = NULL, * copytail = NULL; while (cur) { struct Node* copy = cur->next; struct Node* next = copy->next; //拷贝节点尾插到新链表 if (copyhead == NULL) { copyhead = copytail = copy; } else { copytail->next = copy; copytail = copytail->next; } //恢复原链表 cur->next = next; cur = next; } return copyhead; }
以上便是本文所有内容了，如有错误请各位大佬不吝赐教，感谢留言
