网站建设 摄影服务,涿州李战彪,建设网站网站多少钱,网站系统分析的主要任务包括题目#xff1a; 给定一个链表#xff0c;每个节点包含一个额外增加的随机指针#xff0c;该指针可以指向链表中的任何节点或空节点。 要求返回这个链表的深拷贝。 解题思路#xff1a; 这道题的一个难点就是链表中的随机指针#xff0c;我能想到的就是在这个链表的每个节…题目 给定一个链表每个节点包含一个额外增加的随机指针该指针可以指向链表中的任何节点或空节点。 要求返回这个链表的深拷贝。 解题思路 这道题的一个难点就是链表中的随机指针我能想到的就是在这个链表的每个节点后面都克隆一个相同的节点然后让这两个链表断开连接返回新链表就可以。 思路图解 代码解析
Node* BuyNewNode(int data){Node* ret (Node*)malloc(sizeof(Node));if(ret NULL)assert(0);ret-val data;ret-next NULL;ret-random NULL;return ret;}
class Solution {
public:Node* copyRandomList(Node* head) {if(head NULL)return NULL;//在原链表每一个节点的后面克隆一个新节点Node* pCur head;Node* pNew NULL;while(pCur){pNew BuyNewNode(pCur-val);pNew-next pCur-next;pCur-next pNew;pCur pNew-next;}//更新克隆节点的随机指针域pCur head;while(pCur){pNew pCur-next;if(pCur-random)pNew-random pCur-random-next;pCur pNew-next;}//将克隆的节点开始分离Node* p1 head;Node* p2 head-next;Node* ret head-next;while(p2){p1-next p2-next;p1 p2;p2 p2-next;}return ret;}
};
