Description：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.
Difficulty：如果是一个普通的单链表，我们只要按照顺序一点点复制节点及其next即可，但是当我们这样复制本文的random域时，其节点可能还没有复制出来，这样random就无法指向。
Solution： 1.先把节点一个个的复制出来并且把原来链表对应的节点的next指向这个节点，这样就可以复制出所有的节点，random域指针就可以指向正确的节点，如果原链表的next不指向新节点，那这样的节点就没有意义。 2.把新节点的random域指向它该指的节点，因为我们这时依然可以遍历原链表，当得到原节点random域指向的指针后，可以直接让对应的新节点的random指向原节点random指向的节点对应的新节点，这样新节点random域就成功了。 3.把原节点的next指回原来的next指向节点，同时把新节点的next域也指向新节点，这样一个新的链表就复制完成了。
#include <iostream> #include <fstream> using namespace std; struct RandomListNode { int label; RandomListNode *next, *random; RandomListNode(int x) : label(x), next(NULL), random(NULL) {} }; class Solution { public: RandomListNode *copyRandomList(RandomListNode * head) { RandomListNode * head_cp = nullptr, * cur = head, * cur_cp = nullptr; if (head == nullptr) return nullptr; while (cur != nullptr) { cur_cp = new RandomListNode (cur->label); cur_cp->next = cur->next; cur->next = cur_cp; cur = cur_cp->next; } cur = head; while (cur != nullptr) { cur_cp = cur->next; if (cur->random) cur_cp->random = cur->random->next; cur = cur_cp ->next; } cur = head; head_cp = head->next; while (cur != nullptr) { cur_cp = cur->next; cur->next = cur_cp->next; cur = cur->next; if (cur) cur_cp->next = cur->next; } return head_cp; } };