完整题目链接：https://leetcode-cn.com/problems/copy-list-with-random-pointer/
时间 O(n)，空间 O(1) 的做法参考：https://leetcode-cn.com/problems/copy-list-with-random-pointer/solution/fu-zhi-dai-sui-ji-zhi-zhen-de-lian-biao-c2nvs/
题目要求我们复制一个长度为 n 的链表，该链表除了每个节点有一个指针指向下一个节点外，还有一个额外的指针指向链表中的任意节点或者 null，如下图所示：
如何去复制一个带随机指针的链表？
首先我们可以忽略 random 指针，然后对原链表的每个节点进行复制，并追加到原节点的后面，而后复制 random 指针。最后我们把原链表和复制链表拆分出来，并将原链表复原。
图示过程如下：
1、在每个节点的后面加上它的复制，并将原链表和复制链表连在一起。
2、 从前往后遍历每一个原链表节点，对于有 random 指针的节点 p，我们让它的 p->next->random = p->random->next，这样我们就完成了对原链表 random 指针的复刻。
3、最后我们把原链表和复制链表拆分出来，并将原链表复原。
class Solution { public: Node* copyRandomList(Node* head) { Node *ptr = head; while(ptr) { Node *copy = new Node(ptr -> val); Node *nxt = ptr -> next; ptr -> next = copy; copy -> next = nxt; ptr = nxt; } ptr = head; while(ptr) { if(ptr -> random) { ptr -> next -> random = ptr -> random -> next; } ptr = ptr -> next -> next; } Node *vHead = new Node(-1), *cur = vHead; ptr = head; while(ptr) { Node *nxt = ptr -> next; cur -> next = ptr -> next; ptr -> next = ptr -> next -> next; cur = nxt; ptr = ptr -> next; } auto ret = vHead -> next; delete vHead; return ret; } };
时间 O(n)，空间 O(n) 的比较简单，将整个链表存进 vector，在来一个迭代器与下标的映射即可：
class Solution { public: Node* copyRandomList(Node* head) { while(head) { nodeList.push_back(head); copyNodeList.push_back(new Node(head -> val)); ptrToIdx[head] = nodeList.size() - 1; head = head -> next; } for(int i = 0; i < copyNodeList.size(); ++ i) { if(i > 0) { copyNodeList[i - 1] -> next = copyNodeList[i]; } if(ptrToIdx.find(nodeList[i] -> random) != ptrToIdx.end()) { copyNodeList[i] -> random = copyNodeList[ptrToIdx[nodeList[i] -> random]]; } } return copyNodeList.empty() ? nullptr : copyNodeList.front(); } private: unordered_map<Node*, int> ptrToIdx; // 链表指针与 vector 存放链表的下标映射关系 vector<Node*> nodeList; vector<Node*> copyNodeList; };