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) {} * }; */ class Solution { public: void duplicateList(RandomListNode* head) { if(head==NULL)return; RandomListNode* p = head; while(p) { RandomListNode* tmp = new RandomListNode(p->label); tmp->next = p->next; p->next = tmp; p = tmp->next; } } void setRandom(RandomListNode* head) { if(head==NULL)return; RandomListNode* p = head; RandomListNode* cpy = p->next; while(p) { if(p->random) cpy->random = p->random->next; else cpy->random = NULL; p = cpy->next; if(p) cpy = p->next; } } RandomListNode* separateList(RandomListNode* head) { if(head==NULL)return head; RandomListNode* phead = head->next; RandomListNode* p = head; RandomListNode* p1 = phead; while(p) { p->next = p1->next; p = p->next; if(p){ p1->next = p->next; p1 = p1->next; } } return phead; } RandomListNode *copyRandomList(RandomListNode *head) { // Note: The Solution object is instantiated only once. duplicateList(head); setRandom(head); return separateList(head); } };