国内最全IT社区平台 联系我们 | 收藏本站
华晨云阿里云优惠2
您当前位置:首页 > 互联网 > leetcode - Copy List with Random Pointer

leetcode - Copy List with Random Pointer

来源:程序员人生   发布时间:2014-10-08 09:31:53 阅读次数:2747次

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.

/** * Definition for singly-linked list with a random pointer. * struct RandomListNode { * int label; * RandomListNode *next, *random; * RandomListNode(int x) : label(x), next(NULL), random(NULL) {} * }; */ struct RandomListNode { int label; RandomListNode *next,*random; RandomListNode(int x) : label(x), next(NULL), random(NULL) {} }; class Solution { public: RandomListNode *copyRandomList(RandomListNode *head) { if(head == NULL) return head; //将oldList的每一个节点之后,插入一个newNode. RandomListNode *oldListNode = head; while(oldListNode != NULL) { RandomListNode *newListNode = new RandomListNode(oldListNode->label); newListNode->next = oldListNode->next; newListNode->random = oldListNode->random; oldListNode->next = newListNode; oldListNode = oldListNode->next->next; } //update newListNode上的random结点关联的结点 oldListNode = head; while(oldListNode != NULL) { if(oldListNode->random != NULL) { oldListNode->next->random = oldListNode->random->next; } oldListNode = oldListNode->next->next; } //分离oldListNode与newListNode RandomListNode *newListNode = new RandomListNode(0); newListNode->next = head; oldListNode = head; RandomListNode *resultListNode = newListNode; while(oldListNode != NULL) { newListNode->next = oldListNode->next; oldListNode->next = newListNode->next->next; newListNode = newListNode->next; oldListNode = oldListNode->next; } return resultListNode->next; } };


生活不易,码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生
------分隔线----------------------------
分享到:
------分隔线----------------------------
关闭
程序员人生