[问题描述]
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.
深度拷贝一个带有随机指针的链表
[解题思路]
首先：复制新的节点，插入到对应节点的后面
然后：更新random域，p1->next->random = p1->random->next;
最后：链表拆分出来即可。
1 RandomListNode *Solution::copyRandomList(RandomListNode *head) 2 { 3 if (head == NULL) 4 return head; 5 RandomListNode *p1 = head; 6 RandomListNode *ans = head; 7 while (p1){//复制 8 RandomListNode *tmp = new RandomListNode(p1->label); 9 tmp->next = p1->next; 10 p1->next = tmp; 11 p1 = p1->next->next; 12 } 13 p1 = head; 14 while (p1){//更新random域 15 if (p1->random != NULL){ 16 p1->next->random = p1->random->next; 17 } 18 p1 = p1->next->next; 19 } 20 p1 = head;//链表拆分 21 ans = head->next; 22 RandomListNode *p2 = ans; 23 while (1){ 24 p1->next = p1->next->next; 25 p1 = p1->next; 26 if (p2->next == NULL) 27 break; 28 p2->next = p2->next->next; 29 p2 = p2->next; 31 } 32 return ans; 33 }
leetcode -- Copy List with Random Pointer,布布扣,bubuko.com
leetcode -- Copy List with Random Pointer
原文：http://www.cnblogs.com/taizy/p/3905514.html