首页 > 代码库 > leetcode - Copy List with Random Pointer
leetcode - Copy List with Random Pointer
A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.
Return a deep copy of the list.
个人思路：
1，先遍历一遍链表，创建出复制链表，并且复制链表的next指针已经连接好，同时用一个map存储原结点和新结点的映射关系
2，同时遍历一遍原链表和复制链表，此时关注random指针，根据原结点random指针指向的结点和map表，便可找到对应的复制结点，使复制的random指针指向该复制结点即可
代码：
1 #include <stddef.h> 2 #include <map> 3 4 using namespace std; 5 6 struct RandomListNode 7 { 8 int label; 9 RandomListNode *next, *random;10 RandomListNode(int x) : label(x), next(NULL), random(NULL) {}11 };12 13 class Solution {14 public:15 RandomListNode *copyRandomList(RandomListNode *head) {16 if (!head)17 {18 return NULL;19 }20 21 map<RandomListNode*, RandomListNode*> original2copy; 22 RandomListNode *originalCurrent = head->next;23 RandomListNode *copyHead = new RandomListNode(head->label);24 RandomListNode *copyCurrent = copyHead;25 26 original2copy[head] = copyHead;27 28 while (originalCurrent) //先创建copy结点和连接next指针，并记录配对信息29 {30 copyCurrent->next = new RandomListNode(originalCurrent->label);31 copyCurrent = copyCurrent->next;32 original2copy[originalCurrent] = copyCurrent;33 originalCurrent = originalCurrent->next;34 }35 36 originalCurrent = head;37 copyCurrent = copyHead;38 while (originalCurrent) //连接random指针39 {40 if (originalCurrent->random)41 {42 copyCurrent->random = original2copy[originalCurrent->random];43 }44 45 originalCurrent = originalCurrent->next;46 copyCurrent = copyCurrent->next;47 }48 49 return copyHead;50 }51 };
还有
leetcode - Copy List with Random Pointer
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。