复杂链表的复制
题目链接
思路
如果不考虑random指针的复制，仅仅复制单链表的结构还是简单的。只需要通过一个指针cur遍历原链表，再不断创建新节点尾插到newHead后即可。
但如果要考虑random指针的复制，那过程就复杂了。
有小伙伴会这样想：既然原链表和复制的链表的结构一致，那么对于原链表的任意一个节点，我们都可以先知道它们random指针的指向，这样就可以通过循环得到这是原链表的第几个节点，最后也就可以通过循环将复制链表的相同节点的random指针指向相同的位置了。但是对于每一个节点，每确定一个random指针时间复杂度就是O(N)，一共N个节点时间复杂度就是O(N^2)，显然效率不高。
接下来给大家讲解一个时间复杂度为O(N)，空间复杂度为O(1)的方法：
-
第一步：新建节点，复制链表的
val值、next值这里我们不采用新建一个头
newHead，然后将新建的节点尾插到newHead后的方法。这里我们利用交织链表的方法：
cur遍历原链表，每遍历一个节点就将复制的节点插入到这个节点之后。形象一点来说就是，如果原链表为A->B->C->NULL，那么这一步过后，链表就变成了A->A'->B->B'->C->C'->NULL
struct Node* cur = head;
//先创建交织链表
while (cur)
{
struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
temp->val = cur->val;
temp->next = cur->next;
cur->next = temp;
cur = cur->next->next;
}
-
第二步：完成
random指针的复制实现了上面交织链表的操作，我们就可以直接得到复制链表的节点的
random指着的指向了：即为其原节点
S的随机指针指向的节点T的后继节点T'。需要注意原节点的随机指针可能为空，我们需要特别判断这种情况。通过下图也可以理解对应的关系：
//复制random指针
cur = head;
while (cur)
{
struct Node* temp = cur->random; //找到随机指针的指向
if (temp == NULL)
cur->next->random = NULL;
else
cur->next->random = temp->next;
cur = cur->next->next;
}
-
最后一步，将交织的链表拆成两串链表，返回复制链表的头文章来源：https://www.toymoban.com/news/detail-627939.html
虽然我们也可以不对原链表进行还原，但安全起见，最好不要改变原有的链表结构文章来源地址https://www.toymoban.com/news/detail-627939.html
struct Node* retHead = head->next; //要返回的头节点
struct Node* cur1 = head;
struct Node* cur2 = retHead;
//取消交织，还原为两个链表
while (cur1 && cur2->next)
{
cur1->next = cur1->next->next;
cur2->next = cur2->next->next;
cur1 = cur1->next;
cur2 = cur2->next;
}
cur1->next = NULL;
cur2->next = NULL;
//最后返回复制链表
return retHead;
实现代码
struct Node* copyRandomList(struct Node* head) {
if (head == NULL)
return NULL;
struct Node* cur = head;
//先创建交织链表
while (cur)
{
struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
temp->val = cur->val;
temp->next = cur->next;
cur->next = temp;
cur = cur->next->next;
}
//复制随机指针
cur = head;
while (cur)
{
struct Node* temp = cur->random; //找到随机指针的指向
if (temp == NULL)
cur->next->random = NULL;
else
cur->next->random = temp->next;
cur = cur->next->next;
}
//取消交织
struct Node* retHead = head->next; //要返回的头节点
struct Node* cur1 = head;
struct Node* cur2 = retHead;
//取消交织，还原为两个链表
while (cur1 && cur2->next)
{
cur1->next = cur1->next->next;
cur2->next = cur2->next->next;
cur1 = cur1->next;
cur2 = cur2->next;
}
cur1->next = NULL;
cur2->next = NULL;
//最后返回复制链表
return retHead;
}
到了这里，关于每日一题——复杂链表的复制的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
