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.
题目意思：
深拷贝一个给定的带random指针的链表，这个random指针可能会指向其他任意一个节点或者是为null。
（又是链表啊啊啊啊啊啊啊！！！！！！！！Orz……）
解题思路：
在每个原来节点的后面插入一个新节点（label值一样），然后复制原来节点的random指针，最后包含新旧链表的长链表分成一个原来的链表和一个新的链表。
有一点需要注意：就是遇到链表的问题时，一定要考虑p是空指针时，不要出现p->next之类的调用，本题也是一样要考虑的。
代码如下：
1 class Solution { 2 public: 3 RandomListNode *copyRandomList(RandomListNode *head) { 4 if(head == NULL) 5 return NULL; 6 RandomListNode *p = head; 7 //第一遍：扫描顺序复制next指针 8 while(p){ 9 RandomListNode *newNode = new RandomListNode(p->label); 10 newNode->next = p->next; 11 p->next = newNode; 12 p = newNode->next; 13 } 14 p = head; 15 //第二遍：复制random指针 16 while(p){ 17 if(p->random) 18 p->next->random = p->random->next; 19 p = p->next->next; 20 } 21 p = head; 22 //第三遍：恢复旧链表和新链表 23 RandomListNode *newHead = p->next; 24 RandomListNode *newP = newHead; 25 26 p->next = newP->next; 27 p = p->next; 28 //要保证p不是空指针，不然调用p->next就会报错。 29 while(p){ 30 newP->next = p->next; 31 newP = newP->next; 32 p->next = newP->next; 33 p = p->next; 34 } 35 return newHead; 36 } 37 };
【LeetCode练习题】Copy List with Random Pointer,布布扣,bubuko.com
【LeetCode练习题】Copy List with Random Pointer
原文：http://www.cnblogs.com/4everlove/p/3641652.html