网站建设 部署与发布 答案,wordpress动态图,镇江网站建设教程,路桥网站制作【Leedcode】数据结构中链表必备的面试题#xff08;第五期#xff09; 文章目录【Leedcode】数据结构中链表必备的面试题#xff08;第五期#xff09;1.题目2.思路图解#xff08;1#xff09;第一步#xff1a;复制每一个结点#xff0c;插入到原结点和下一个结点之…【Leedcode】数据结构中链表必备的面试题第五期 文章目录【Leedcode】数据结构中链表必备的面试题第五期1.题目2.思路图解1第一步复制每一个结点插入到原结点和下一个结点之间2第二步根据原结点random处理复制结点的random2第三步复制结点解下来连接成一个新链表恢复原链表链接关系3.整体源代码总结1.题目 复制带随机指针的链表 如下示例 给你一个长度为n的链表每个节点包含一个额外增加的随机指针random该指针可以指向链表中的任何节点或空节点。构造这个链表的深拷贝。深拷贝应该正好由n个全新节点组成其中每个新节点的值都设为其对应的原节点的值。
新节点的next指针和random指针也都应指向复制链表中的新节点并使原链表和复制链表中的这些指针能够表示相同的链表状态。
复制链表中的指针都不应指向原链表中的节点 。 返回复制链表的头节点。简单来说复制原来的链表新的返回新链表的头结点 2.思路图解
1第一步复制每一个结点插入到原结点和下一个结点之间 第一步代码实现 如下示例 //1.第一步先把原来的拷贝一份struct Node* cur head;while(cur){struct Node* copy (struct Node*)malloc(sizeof(struct Node));copy - next cur - next;cur - next copy;copy - val cur - val;cur copy - next;}2第二步根据原结点random处理复制结点的random
这里要注意复制完之后的random所指向的是复制之前random的next具体如下图 第二步代码实现 如下示例 // 2.第二步把random拷贝过去cur head; while(cur){struct Node* copy cur - next;if(cur - random NULL){copy - random NULL;}else{copy - random cur - random - next;}cur copy - next;}2第三步复制结点解下来连接成一个新链表恢复原链表链接关系 第三步代码实现 如下示例 // 3.第三步把拷贝结点解下来链接成新的链表同时恢复原链表cur head;struct Node* copyhead NULL ,*copytail NULL;while(cur){struct Node* copy cur - next;struct Node* next copy - next;if(copytail NULL){copytail copyhead copy;}else{copytail - next copy;copytail copy;}//恢复原链表的犍cur - next next;cur next ;}3.整体源代码 整体源代码 如下示例 struct Node
{int val;struct Node *next;struct Node *random;
};
struct Node* copyRandomList(struct Node* head)
{//1.第一步先把原来的拷贝一份struct Node* cur head;while(cur){struct Node* copy (struct Node*)malloc(sizeof(struct Node));copy - next cur - next;cur - next copy;copy - val cur - val;cur copy - next;}// 2.第二步把random拷贝过去cur head; while(cur){struct Node* copy cur - next;if(cur - random NULL){copy - random NULL;}else{copy - random cur - random - next;}cur copy - next;}// 3.第三步把拷贝结点解下来链接成新的链表同时恢复原链表cur head;struct Node* copyhead NULL ,*copytail NULL;while(cur){struct Node* copy cur - next;struct Node* next copy - next;if(copytail NULL){copytail copyhead copy;}else{copytail - next copy;copytail copy;}//恢复原链表的犍cur - next next;cur next ;}return copyhead;
}总结
以上就是今天要讲的内容本文介绍了【Leedcode】数据结构中链表必备的面试题第五期。 如果我的博客对你有所帮助记得三连支持一下感谢大家的支持
