66. Plus One
题目描述：
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.
题目翻译
深拷贝一个链表，该链表除了含有next指针外，还包含一个random指针，该指针指向字符串中的某个节点或者为空
《剑指offer》上的面试题26
解题方案
标签： Hash Table
思路：
考虑l1作为第一个列表中的节点，l2作为第二个列表中的相应节点:
Step1 为l1的每个节点创建一个新节点来构建l2,并且将l2的相应节点后移一个位置, 于是l2中新的头节点是第二个节点
Step2 修正l2中的随机指针,记住l1-> next实际上是l2; l2-> random将是l2中的对应于l1-> random的下一个节点
Step3 将组合列表分为2个,拼接出l2的所有节点,最后返回步骤2中保存的新头节点
代码：
class Solution {
public:
unordered_map<RandomListNode*, RandomListNode*>mp;
RandomListNode *copyRandomList(RandomListNode *head) {
RandomListNode *newHead, *l1, *l2;
if (head == NULL) return NULL;
for (l1 = head; l1 != NULL; l1 = l1->next->next) {
l2 = new RandomListNode(l1->label);
l2->next = l1->next;
l1->next = l2;
}
newHead = head->next;
for (l1 = head; l1 != NULL; l1 = l1->next->next) {
if (l1->random != NULL) l1->next->random = l1->random->next;
}
for (l1 = head; l1 != NULL; l1 = l1->next) {
l2 = l1->next;
l1->next = l2->next;
if (l2->next != NULL) l2->next = l2->next->next;
}
return newHead;
}
};