# 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:
15         if ( !head ) {
16             return NULL;
17         }
21         int count = 1;
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         }
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         }
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:
12         if( NULL == head ) {
13             return NULL;
14         }
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         }
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         }
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         }