这道题目首先不管random指针，按照next指针把链表元素给复制出来。然后处理random指针，比较容易想到的想法是利用哈希思想(或者等价的map，set等stl容器)，但这样的话需要辅助空间。

不需要辅助空间的方法，复制元素的时候把原始链表改成这样就可以了：

然后修改新增元素的random指针，再把这个链表拆开，返回新链表。

1 class Solution { 2 public: 3     RandomListNode* Clone(RandomListNode* pHead) 4     { 5         if(pHead==NULL) 6             return NULL; 7         RandomListNode* root=pHead; 8         while(root) 9         {10             RandomListNode* p=new RandomListNode(root->label);11             p->next=root->next;12             root->next=p;13             root=p->next;14         }15         root=pHead;16         while(root)17         {18             if(root->random!=NULL)19                 root->next->random=root->random->next;20             root=root->next->next;21         }22         RandomListNode* result=pHead->next;23         RandomListNode* prev=result;24         root=pHead;25         while(root->next->next!=NULL)26         {27             root->next=prev->next;28             root=root->next;29             prev->next=prev->next->next;30             prev=prev->next;31         }32         root->next=NULL;33         return result;34     }35 };