复制随机链表
例题：leetcode138
这是一个深拷贝问题，单链表的复制很简单，真正麻烦的是random指针。
step1复制链表
有如图两种思路：
仔细思考：如果像上方一样分开复制为两个链表，那么在复制random指针是，每次复制一个random指针，就需要在新链表中进行一次遍历，
查找到新链表中对应random所指向的结点。所以遍历的次数会随着random指针的数量而增长，造成浪费。
核心问题：如何更快的搜索到新链表中与原链表random指针指向的结点值相同的结点。
例如假设原链表为1->2->3->4，其中1的random指向4 。那么在复制的新链表中，在复制1这个结点时，就需要去找到新链表中的4结点，这就需要进行一次遍历。造成了时间上的浪费。
那么再看看第二种复制方式（交叉复制）
图中红色部分是复制的新节点。如果使用这种方式进行复制，形成old-new-old-new-old-new的链表结构，就可以如下图更轻易地找到要复制的random指针指向的结点。
对应操作：
// 复制random指针
curr = head;
while (curr) {
// 如图中所示
if(curr->random){
curr->next->random = curr->random->next;
}
// curr 一步两跳保证curr在遍历旧链表
curr = curr->next->next;
}
到此已经完成了数据域和random指针的深拷贝。
step 2拆分链表
拆分的逻辑较为简单如图所示：
首先确认新旧头节点，curr从旧结点开始遍历，curr->next作为新链表的头节点。每次将curr指针指向其nextNode的后继。完成操作后将curr向后移动一个节点，直到curr的后继为空。
// 新旧链表的拆分
curr=head;
Node*newHead=head->next;
while(curr->next){
Node*nextNode=curr->next;
curr->next=nextNode->next;
//curr向后移动一位
curr=nextNode;
}
完整代码如下
class Solution {
public:
Node* copyRandomList(Node* head) {
if(head==nullptr){
return head;
}
Node* curr = head;
// 复制当前节点并插入当前节点的后方
// old-new-old-new-old-new
while (curr) {
Node* newNode = new Node(curr->val);
Node* nextNode = curr->next;
curr->next = newNode;
newNode->next = nextNode;
curr = nextNode;
}
// 复制random指针
curr = head;
while (curr) {
// 如图中所示
if(curr->random){
curr->next->random = curr->random->next;
}
// curr 一步两跳保证curr在遍历旧链表
curr = curr->next->next;
}
// 新旧链表的拆分
curr=head;
Node*newHead=head->next;
while(curr->next){
Node*nextNode=curr->next;
curr->next=nextNode->next;
curr=nextNode;
}
return newHead;
}
};