copy list with rndom pointer

copy list with rndom pointer

Solution one

Using two maps, first one save the (RandomListNode*,index) pair of original list, the second save (index,RandomListNode*) pair of new list.

 1 /**
 2  * Definition for singly-linked list with a random pointer.
 3  * struct RandomListNode {
 4  *     int label;
 5  *     RandomListNode *next, *random;
 6  *     RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
 7  * };
 8  */
 9 class Solution {
10 private:
11     map < RandomListNode*,int > originMap;
12     map < int , RandomListNode* > newMap;
13 public:
14     RandomListNode *copyRandomList(RandomListNode *head) {
15         if ( !head ) {
16             return NULL;
17         }
18         RandomListNode* newHead = new RandomListNode(head->label);
19         originMap[head] = 0;
20         newMap[0] = newHead; 
21         int count = 1;
22         RandomListNode* p = head;
23         RandomListNode* q = newHead;
24         RandomListNode* node = NULL;
25         while ( p->next ) {
26             p = p->next;
27             node = new RandomListNode(p->label);
28             originMap[p] = count;
29             newMap[count] = node;
30             q->next = node;
31             q = q->next;
32             count++;
33         }
34         p = head;
35         q = newHead;
36         while ( p ) {
37             if ( p->random ) {
38                 int randNum = originMap[p->random];
39                 q->random = newMap[randNum];
40             }
41                 p = p->next;
42                 q = q->next;
43         }
44         return newHead;
45     }
46 };

Solution two better

For each node in origin list, insert a new list behind it and the new node has the same label with the origin node. Go through this new list, if the origin node has a random pointer and the new node's random pointer should point to the next of the target which the origin one's random pointer points to.

 1 /**
 2  * Definition for singly-linked list with a random pointer.
 3  * struct RandomListNode {
 4  *     int label;
 5  *     RandomListNode *next, *random;
 6  *     RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
 7  * };
 8  */
 9 class Solution {
10 public:
11     RandomListNode *copyRandomList(RandomListNode *head) {
12         if( NULL == head ) {
13             return NULL;
14         }
15         RandomListNode* p = head;
16         RandomListNode* q = NULL;
17         while ( p ) {
18             q = new RandomListNode(p->label);
19             q->next = p->next;
20             p ->next = q;
21             p = q->next;
22         }
23         RandomListNode* newHead = head->next;
24         p = head;
25         q = newHead;
26         RandomListNode* nextP = NULL;
27         RandomListNode* nextQ = NULL;
28         while ( p ) {
29             nextP = q->next;
30             if ( nextP ) {
31                 nextQ = nextP->next;
32             } else {
33                 nextQ = NULL;
34             }
35             if ( p->random ) {
36                 q->random = p->random->next;
37             }
38             p = nextP;
39             q = nextQ;
40         }
41         p = head;
42         q = newHead;
43         while ( p ) {
44             nextP = q->next;
45             if ( nextP ) {
46                 nextQ = nextP->next;
47             } else {
48                 nextQ = NULL;
49             }
50             p->next = nextP;
51             q->next = nextQ;
52             p = p->next;
53             q = q->next;
54         }
55         return newHead;
56     }
57 };

Loading Disqus comments...
Table of Contents