数据结构 ——— 单链表oj题：复制带随机指针的链表
目录
题目要求
一个长度为 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.控制拷贝节点的random
cur = 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)
原文地址：https://blog.csdn.net/weixin_55341642/article/details/142884025
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！