LeetCode题解之Copy List with Random Pointer

1、题目描述

2、问题分析

首先要完成一个普通的单链表的深度复制，然后将一个旧的单链表和新的单链表的节点使用map对应起来，最后，做一次遍历即可。

3、代码

 1 RandomListNode *copyRandomList(RandomListNode *head) {
 2        if( head == NULL){
 3            return NULL;
 4        }
 5         RandomListNode* newhead = new RandomListNode(0);
 6         RandomListNode* np = newhead;
 7         
 8         RandomListNode* p = head;
 9         map<RandomListNode*, RandomListNode*> m;
10         while (p != NULL){
11             RandomListNode* tmp = new RandomListNode(p->label);
12             m.insert(make_pair(p,tmp));
13             np->next = tmp;
14             np = np->next;
15             p = p->next;
16         }
17         
18         p = head ;
19         np = newhead->next;
20         while( p != NULL){
21             np->random = m[p->random];
22             p = p->next;
23             np = np->next;
24         }
25         return newhead->next;
26         
27     }