复杂链表的复制
C++，链表深拷贝。
这里可以直接在原链表上扩充，然后分裂成两个链表。
- 将原链表的每个结点复制一份并放每个结点之后，比如[1, 2, 3, 4, null]—>[1， 1， 2， 2， 3， 3， 4， 4， null]；
- 然后遍历每个原结点，让其拷贝结点的random指针指向其random结点的拷贝结点。比如[1， 1， 2， 2， 3， 3， 4， 4， null]中，第一个元素
1的random指针指向第5个元素3，那就应该让第二个元素1的random指针指向第6个元素3； - 然后将偶数位结点全部分裂出来，这样就变成了两个链表了，返回新链表头结点指针。
代码：
/*
struct RandomListNode {
int label;
struct RandomListNode *next, *random;
RandomListNode(int x) :
label(x), next(NULL), random(NULL) {
}
};
*/
class Solution {
public:
RandomListNode* Clone(RandomListNode* pHead) {
if (!pHead) return nullptr;
using node = RandomListNode;
node *cur = pHead;
while (cur) {
node *cp = new node(cur->label);
cp->next = cur->next;
cur->next = cp;
cur = cp->next;
}
node *new_head = pHead->next;
cur = pHead;
while (cur) {
if (cur->random)
cur->next->random = cur->random->next;
cur = cur->next->next;
}
cur = pHead;
while (cur->next) {
node *next = cur->next;
if (next->next)
cur->next = next->next;
else
cur->next = nullptr;
cur = next;
}
return new_head;
}
};
