目录
题目要求
手搓带随机指针的链表
代码实现
题目要求
一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 tandom ，该指针可以指向链表中的任何节点或空节点
构造这个链表的 深拷贝，深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值，新节点的 next 指针和 random 指针也都应该指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态，复制链表中的指针都不应指向原链表中的节点
例如：如果原链表中有 x 和 y 两个节点，其中 x.random --> y ，那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y
最后返回复制链表的头节点
手搓带随机指针的链表
代码演示：
struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(n1);
struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(n2);
struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(n3);
struct ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(n4);
struct ListNode* n5 = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(n5);n1->val = 7;
n2->val = 13;
n3->val = 11;
n4->val = 10;
n5->val = 1;n1->next = n2;
n2->next = n3;
n3->next = n4;
n4->next = n5;
n5->next = NULL;n1->random = NULL;
n2->random = n1;
n3->random = n5;
n4->random = n3;
n5->random = n1;代码实现
代码演示：
struct ListNode* copyRandomList(struct ListNode* head)
{// 1.拷贝节点插入到对应的原节点后面struct ListNode* cur = head;while (cur != NULL){struct ListNode* copy = (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* next = cur->next;// 插入copy->val = cur->val;cur->next = copy;copy->next = next;// 迭代cur = next;}// 2.控制拷贝节点的randomcur = head;while (cur != NULL){struct ListNode* copy = cur->next;// 判断并复制if (cur->random == NULL){copy->random = NULL;}else{copy->random = cur->random->next;}// 迭代cur = copy->next;}// 3.链接拷贝节点cur = head;struct ListNode* copyHead = NULL;struct ListNode* copyTail = NULL;while (cur != NULL){struct ListNode* copy = cur->next;struct ListNode* next = copy->next;// 尾插if (copyHead == NULL){copyHead = copyTail = copy;}else{copyTail->next = copy;copyTail = copyTail->next;}// 恢复原链表cur->next = next;// 迭代cur = next;}return copyHead;
}代码解析：
代码思路：拷贝 head 链表的所有节点并不难，难的是 head 节点中的 random 的指向，解决办法办法就是将每个拷贝节点一一链接在原节点的后面，如图所示：
这样就能通过原链表的 random 和拷贝链表的 random 对应链接（当原节点的 random 指向的是 NULL 时，对应的拷贝节点的 random 要同样指向 NULL），其他情况时：
核心代码：copy->random = cur->random->next;
代码逻辑：先把拷贝节点一一链接到原链表节点后，再控制 random 指针的指向，最后再让拷贝节点一一链接，并且恢复原节点
代码验证：
算法的时间和空间复杂度：
有 3 个 while 循环，每个 while 内部执行了常数次，所以是 3*N （去掉常数项）
额外开辟了一个和 head 链表一样长的链表，所以是 N，得出
时间复杂度：O(N)
空间复杂度：O(N)