全程营销网站建设公司,网站建设入账,青海省建设网站价格低,网站备案幕布尺寸前言 随机链表的复制涉及到复制一个链表#xff0c;该链表不仅包含普通的next指针#xff0c;还包含random指针#xff0c;该指针指向链表中的任意节点或空节点。 文章目录 原地修改链表 题目链接#xff1a;
LeetCode 138. 随机链表的复制 原地修改链表 题目介绍#xf… 前言 随机链表的复制涉及到复制一个链表该链表不仅包含普通的next指针还包含random指针该指针指向链表中的任意节点或空节点。 文章目录 原地修改链表 题目链接
LeetCode 138. 随机链表的复制 原地修改链表 题目介绍 给你一个长度为 n 的链表每个节点包含一个额外增加的随机指针 random 该指针可以指向链表中的任何节点或空节点。 构造这个链表的深拷贝。 深拷贝应该正好由 n 个全新节点组成其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。 例如如果原链表中有 X 和 Y 两个节点其中 X.random - Y 。那么在复制链表中对应的两个节点 x 和 y 同样有 x.random - y 。 返回复制链表的头节点。 用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示 val一个表示 Node.val 的整数。 random_index随机指针指向的节点索引范围从 0 到 n-1如果不指向任何节点则为 null 。 示例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;}
}如果你喜欢这篇文章点赞评论关注⭐️哦 欢迎大家提出疑问以及不同的见解。
