首页 > 其他 > 详细

Copy List with Random Pointer

时间:2014-05-30 15:08:26      阅读:469      评论:0      收藏:0      [点我收藏+]

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.

bubuko.com,布布扣
/**
 * 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) {}
 * };
 */
class Solution {
public:
    RandomListNode *copyRandomList(RandomListNode *head) 
    {
        //insert copy
        if(head==NULL) return NULL;
        RandomListNode* p=head;
        while(p!=NULL)
        {
            RandomListNode* pnext=p->next;
            RandomListNode* pnew=new RandomListNode(p->label);
            p->next=pnew;
            pnew->next=pnext;
            p=pnext;
        }
        //the pointer
        RandomListNode* p1=head;
        RandomListNode* p2=head->next;
        while(true)
        {
            if(p1->random!=NULL) p2->random=p1->random->next;
            p1=p1->next->next;
            if(p1==NULL) break;
            p2=p2->next->next;
        }
        //split the 2 list
        RandomListNode* phead=head->next;
        p1=head;
        p2=phead;
        while(true)
        {
            RandomListNode* p1next=p1->next->next;
            p1->next=p1next;
            if(p1next==NULL) break;
            p2->next=p1next->next;
            
            p1=p1next;
            p2=p1next->next;
        }
        return phead;
    }
};
bubuko.com,布布扣

 

Copy List with Random Pointer,布布扣,bubuko.com

Copy List with Random Pointer

原文:http://www.cnblogs.com/erictanghu/p/3759703.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!