注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

HT·生活

123

 
 
 

日志

 
 

ex138 Copy List with Random Pointer  

2015-05-27 23:11:12|  分类: leetcode |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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.


深度copy一个带有随机指针的链表,实际上这是一个有向图,不过简化为链表的形式。这里面没有说label是独一无二的,所以不能用label作为key。
需要遍历两边list,第一遍把next的节点规划话,比较存两个map,一个是记录随机指针的指向,另一个是旧链表和新链表的映射关系。需要搞清楚每个map的key,random pointer指向的内容不能作为key,因为可能多个指向一个,而每个节点只有一个random pointer,可以作为key。

class Solution {
public:

RandomListNode *copyRandomList(RandomListNode *head) {
RandomListNode * newHead = traverse(head);
return newHead;
}
RandomListNode * traverse(RandomListNode *head)
{
map<RandomListNode *, RandomListNode *>map1,map2,map3;
//map1 映射 旧链表随机指针之间的关系
//map2 映射 新旧链表节点之间的关系
//map3 映射 新链表随机指针之间的关系

RandomListNode *current = NULL, *newHead = NULL,*p=NULL,*randomPointer=NULL;
current = head;
while (current != NULL)
{
p = (struct RandomListNode*)malloc(sizeof(struct RandomListNode));
p->next = NULL;
p->random = NULL;
p->label = current->label;
if (current->random != NULL)
{
map1.insert(pair<RandomListNode *, RandomListNode *>(current, current->random));
}
map2.insert(pair<RandomListNode *, RandomListNode *>(current,p)); //所有的节点都map上
if (current == head)
{
pre = p;
newHead = p;
}
else
{
pre->next = p;
pre = pre->next;
}
current = current->next;
}

current = head;
p = newHead;
while (current != NULL)
{
if (map1.find(current) != map1.end())
{
randomPointer = map1[current]; //通过map1找到 current的random节点
map3.insert(pair<RandomListNode *, RandomListNode *>(map2[current], map2[randomPointer]));
map2[current]->random = map2[randomPointer]; //通过map2找到 对应current那个节点的 random节点
}
current = current->next;
//p = p->next;
}
return newHead;
}
};


  评论这张
 
阅读(25)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017