题目的关键是要让新链表和原有链表发送关联，可以通过这种关联来设置新链表的random pointer

思路：将新链表的元素插入到原有链表元素的后面，如下图所示，就可以根据原有链表的radom->next 就是新链表的random指针

所以分3步骤：

1 新元素插入

2 设置新链表的random

3 拆分大链表，回复old link 和new link

 

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  10 class Solution {11 public:12     RandomListNode *copyRandomList(RandomListNode *head) {13         14         RandomListNode* pOld = head;15         RandomListNode* pNew = NULL;16         RandomListNode* pRes = NULL;17         18         if(head == NULL) return NULL;19         20         // insert every new node after old new node21         while(pOld)22         {23             pNew = new RandomListNode(pOld->label);24             if(pOld == head) pRes = pNew;25             pNew->next = pOld->next;26             pOld->next = pNew;27             pOld = pNew->next;28         }29         30 31         pOld = head;32         // constrct new's random pointer33         while(pOld)34         {35             pNew = pOld->next;36             if(pOld->random == NULL)37                 pNew->random == NULL;38             else 39                 pNew->random = pOld->random->next;40             pOld = pNew->next;41         }42 43 44         // recover old's and new's next pointer45         //恢复old list 和new list46   47         pOld = head;48         49         while(pOld)50         {51             pNew = pOld->next;52             if(pNew == NULL)53                 pOld->next = NULL;54             else55                 pOld->next = pNew->next;56             pOld = pNew;57         }58 59         return pRes;   60     }61 };