专业做营销网站,深圳做外贸网站,石家庄网页制作招聘信息,制作ppt的软件电脑每日一题#xff08;复制带随机指针的链表#xff09;
138. 复制带随机指针的链表 - 力扣#xff08;LeetCode#xff09; 思路#xff1a; 由于每个链表还包含了一个random节点指向了链表中的随机节点#xff0c;所以并不能直接照搬复制原链表。首先想到的暴力思路是复…每日一题复制带随机指针的链表
138. 复制带随机指针的链表 - 力扣LeetCode 思路 由于每个链表还包含了一个random节点指向了链表中的随机节点所以并不能直接照搬复制原链表。首先想到的暴力思路是复制一条新的链表。找到原链表的每个节点的random到该节点的相对举例。但是实际上操作起来更复杂。 这里提供另外一个思路 第一步创建新节点 在原链表的每个节点之后紧跟着复制一个节点形成新老节点相间的局面并且将原链表的每个节点的值赋值给其后创建的节点中并且将新开辟的节点的random成员的值设置为NULL如下图 第二步设置新节点random的值 创建一个cur指针指向原链表的第一个节点再创建一个newhead指针指向cur的nextcur指针从head处出发newhead从head-next处出发。开始遍历链表。这里有一个最重要的关系当cur-random不为空时当cur-random的值为NULL时则不做改动满足cur-random与cur的对应关系与newhead-random和cur-random-next的对应关系时一样的。 就可以根据这些对应关系修改新创建的节点的random的值。接着cur向后移动两步指向下一个原链表中的节点newhead也向后走两步指向下一个新开辟的节点。如下图所示红色的是random指针绿色的是next指针新节点之间的random的链接关系和原链表的random的链接关系并没有改变。 第三步断开链表 创建三个指针cur1和cur2和newheadcur1从head的next处开始遍历cur2从head处开始遍历newhead指针用于记录cur1的起始位置。将原链表的节点和新链表的节点各自分成一条链表。特别注意这里的遍历迭代的顺序不得交换 在两个指针向后更新的过程中肯定是cur1-next先为NULL当cur1-next为NULL时就退出循环但是此时的cur2的next指针仍然指向的是新开辟的最后一个节点。所以在返回newhead之前要将cur2-next置为NULL。 代码实现 if(headNULL){return NULL;}struct Node* cur head;struct Node* curNext head;struct Node* newhead head;//构造相间的节点while(cur!NULL){curNext cur-next;struct Node* newnode (struct Node*)malloc(sizeof(struct Node));if(newnode NULL)return NULL;newnode-val cur-val;newnode-random NULL;//新节点链接在原节点之后cur-next newnode;newnode-next curNext;cur curNext;}cur head;//复制各自的randomwhile(cur!NULL){newhead cur-next;if(cur-random!NULL){newhead-random cur-random-next;}cur cur-next-next;}//断开newhead head-next;struct Node* cur1 newhead;//cur1用于遍历newnodestruct Node* cur2 head;//cur2用于遍历原链表的节点while(cur1-next){cur2-next cur2-next-next;cur1-next cur1-next-next;cur2 cur2-next; cur1 cur1-next;}//将cur2-next置空cur2-next NULL;return newhead;完结
复制带随机指针的链表习题的分析就到这里啦若有不足欢迎评论区指正下期见
