国内免费域名注册网站,无极官方网,公众号开发答题活动,腾讯企业邮箱官网登录入口力扣138 随机链表的复制
题目描述
给你一个长度为 n 的链表#xff0c;每个节点包含一个额外增加的随机指针 random #xff0c;该指针可以指向链表中的任何节点或空节点。
构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成#xff0c;其中每个新节点的值都…力扣138 随机链表的复制
题目描述
给你一个长度为 n 的链表每个节点包含一个额外增加的随机指针 random 该指针可以指向链表中的任何节点或空节点。
构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
例如如果原链表中有 X 和 Y 两个节点其中 X.random -- Y 。那么在复制链表中对应的两个节点 x 和 y 同样有 x.random -- y 。
返回复制链表的头节点。 思路分析
有很多小伙连题目都读不懂更别说思路。下面我将进行解释
其实就是一个关于链表的拷贝像一般的单链表只需要遍历一遍复制即可但这个链表多了一个随机指针random它可以指向链表中的任意一个结点包括它自己同时也可以指向空。这时你可能会想到将链表复制一遍放到新节点再将random指向对应的源节点的位置不就行了但题目要求复制链表中的指针都不应指向原链表中的节点 这就成了一个大问题。也就是说如果碰到后面结点的random在它之前且不知道是是什么位置单纯的用什么所谓的双指针还是快慢指针都会很麻烦。
基于单链表这题的最优解是
将要复制的结点插入到每一个源节点的后面记为copy题目要求copy的random不能指回源节点只能值向复制的结点会发现如果要取到对应的复制结点例如原节点13的random指向7那复制结点13也要指向复制的7怎么取到呢就是原结点13的random的next是不是很巧妙基于这个思路即复制结点的random就是原结点的random的next值。 方法步骤
1.将需要复制的结点插入到原结点的后面。
2.将复制结点的random指向原结点的random的next值。
3.将链表取下恢复原链表。
struct Node* copyRandomList(struct Node* head) {struct Node* curhead;//保存头结点用cur遍历while(cur){struct Node* copy(struct Node*)malloc(sizeof(struct Node));//复制结点用malloc创建copy-valcur-val;//copy-nextcur-next;//进行插入cur-nextcopy;curcopy-next;//往下走}curhead;//再从头走一遍while(cur)//处理random指针{struct Node* copycur-next;struct Node* nextcopy-next;if(cur-randomNULL){copy-randomNULL;}else{copy-randomcur-random-next;}curnext;}curhead;struct Node* newheadNULL,*tailNULL;while(cur)//将复制完后的链表取下{struct Node* copycur-next;struct Node* nextcopy-next;//保存原链表的next值if(newheadNULL)//尾插{newheadtailcopy;}else{tail-nextcopy;tailtail-next;}cur-nextnext;//恢复原链表curnext;//往下走}return newhead;//返回新节点
}
