# Copy List with Random Pointer

> 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.

```c++
class Solution {
public:
return NULL;
}

RandomListNode dummy(0);
RandomListNode* n = &dummy;
map m;
while(h) {
RandomListNode* node = new RandomListNode(h->label);
n->next = node;
n = node;

node->random = h->random;

m[h] = node;

h = h->next;
}

h = dummy.next;
while(h) {
if(h->random != NULL) {
h->random = m[h->random];
}
h = h->next;
}

return dummy.next;
}
};
```

```
|------------|
| v
1 --> 2 --> 3 --> 4

```

```
|--------------------------|
| v
1 --> 1' --> 2 --> 2' --> 3 --> 3' --> 4 --> 4'
| ^
|-------------------|
```

```
|--------------------------|
| v
1 --> 1' --> 2 --> 2' --> 3 --> 3' --> 4 --> 4'
| ^
|-------------------------|
```

```c++
class Solution {
public:
return NULL;
}

//遍历并插入新的节点
RandomListNode* n = NULL;
while(h) {
RandomListNode* node = new RandomListNode(h->label);
node->random = h->random;

n = h->next;

h->next = node;
node->next = n;
h = n;
}

//调整random
while(h) {
if(h->random != NULL) {
h->random = h->random->next;
}
if(!h->next) {
break;
}
h = h->next->next;
}

//断开链表
RandomListNode dummy(0);
RandomListNode* p = &dummy;
while(h) {
n = h->next;
p->next = n;
p = n;
RandomListNode* nn = n->next;
h->next = n->next;
h = n->next;
}

return dummy.next;
}
};
```