我要评论
文章目录
题目链接： leetcode 138. 随机链表的复制
原地修改链表
示例1：
输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
示例2：
输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]
- 第一次遍历：复制节点并插入到原节点后面
- 对于每个原节点，创建一个新节点，并将新节点插入到原节点后面。
- 新节点的val和next指针与原节点相同，而random指针初始化为null。
struct node* current = head;
while (current != null) {
struct node* copy = (struct node*)malloc(sizeof(struct node));
copy->val = current->val;
copy->next = current->next;
copy->random = null;
current->next = copy;
current = copy->next;
}
-
第二次遍历：更新复制节点的 random 指针
- 对于每个原节点，如果其random指针不为null，则将对应的复制节点的random指针指向原节点的random指针的下一个节点。
current = head;
while (current != null) {
if (current->random != null) {
current->next->random = current->random->next;
}
current = current->next->next;
}
-
第三次遍历：拆分原链表和复制链表
- 将链表拆分为原链表和复制链表，同时恢复原链表的next指针。
struct node* newhead = head->next;
struct node* newcurrent = newhead;
current = head;
while (current != null) {
current->next = newcurrent->next;
current = current->next;
if (current != null) {
newcurrent->next = current->next;
newcurrent = newcurrent->next;
}
}
如果你喜欢这篇文章，点赞👍+评论+关注⭐️哦！
欢迎大家提出疑问，以及不同的见解。
发表评论