[刷题记录2]随机链表的复制
- 题目信息：
- 题目思路(环境来自力扣OJ的C语言)：
- 复杂度：
- 代码和解释：
- 1.遍历一遍原链表的同时，在每个原节点后面插入一个相同的新节点，共插入 n 个新节点。
- 2.利用两者联系，当原节点 random 指向非空节点时，新节点 random 指向为原节点 random->next。
- 3.将原链表和新链表分开。
- 完整代码
题目信息：
给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。
构造这个链表的 深拷贝。 深拷贝应该正好由 n 个全新节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
题目参考：
力扣：138. 随机链表的复制
牛客网：JZ35 复杂链表的复制
题目思路(环境来自力扣OJ的C语言)：
1.遍历一遍原链表的同时，在每个原节点后面插入一个相同的新节点，共插入 n 个新节点。
2.利用两者联系，当原节点 random 指向非空节点时，新节点 random 指向为原节点 random->next。
3.将原链表和新链表分开。
复杂度：
时间复杂度：O(n)
空间复杂度：O(1)
空间复杂度考虑的是算法本身使用的空间消耗，题目中由于拷贝产生的O(n)空间为题目本身要求，则不计入。
代码和解释：
1.遍历一遍原链表的同时，在每个原节点后面插入一个相同的新节点，共插入 n 个新节点。
typedef struct Node Node;
struct Node* copyRandomList(struct Node* head) {
if (head == NULL) // 为空直接返回
return NULL;
Node* cur = head;
while (cur) // 当cur == NULL时退出
{
Node* temp = (Node*)malloc(sizeof(Node)); // 1.创建新节点
temp->val = cur->val; // 并拷贝值
temp->next = cur->next; // 2.将新节点temp->next 指向 cur->next
cur->next = temp; // 3.将cur->next 指向 temp
cur = temp->next; // 4.cur移动到temp->next的位置
}
}
2.利用两者联系，当原节点 random 指向非空节点时，新节点 random 指向为原节点 random->next。
cur = head; // cur 回到头节点
while (cur) // 拷贝 random
{
if (cur->random == NULL) // 1.当cur->random为空
cur->next->random = NULL; // 置空
else
cur->next->random = cur->random->next; // 2.当cur->random不为空
// 可用三目操作符简写成下式
// cur->next->random = (cur->random ? cur->random->next : NULL);
cur = cur->next->next; // 3.移动到下一个原节点
}
3.将原链表和新链表分开。
cur = head; // cur 回到头节点
Node* newHead = head->next; // 1.保存新节点的头
Node* temp = newHead;
while (cur) // 将两个链表复原
{
cur->next = temp->next; // 2.恢复原节点next指向
cur = cur->next; // 2.2.移动到下一个原节点
temp->next = (cur ? cur->next : cur); // 3.恢复新节点next指向
temp = temp->next; // 3.2.移动到下一个新节点
}
完整代码
typedef struct Node Node;
struct Node* copyRandomList(struct Node* head) {
if (head == NULL) // 为空直接返回
return NULL;
Node* cur = head;
while (cur) // 当cur == NULL时退出
{
Node* temp = (Node*)malloc(sizeof(Node)); // 1.创建新节点
temp->val = cur->val; // 并拷贝值
temp->next = cur->next; // 2.将新节点temp->next 指向 cur->next
cur->next = temp; // 3.将cur->next 指向 temp
cur = temp->next; // 4.cur移动到temp->next的位置
}
cur = head; // cur 回到头节点
while (cur) // 拷贝 random
{
if (cur->random == NULL) // 1.当cur->random为空
cur->next->random = NULL; // 置空
else
cur->next->random = cur->random->next; // 2.当cur->random不为空
// 可用三目操作符简写成下式
// cur->next->random = (cur->random ? cur->random->next : NULL);
cur = cur->next->next; // 3.移动到下一个原节点
}
cur = head; // cur 回到头节点
Node* newHead = head->next; // 1.保存新节点的头
Node* temp = newHead;
while (cur) // 将两个链表复原
{
cur->next = temp->next; // 2.恢复原节点next指向
cur = cur->next; // 2.2.移动到下一个原节点
temp->next = (cur ? cur->next : cur); // 3.恢复新节点next指向
temp = temp->next; // 3.2.移动到下一个新节点
}
return newHead; // 返回新节点的头
}
