题目地址：https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof/
请实现copyRandomList函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个next指针指向下一个节点，还有一个random指针指向链表中的任意节点或者null。
示例 1：
输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
示例 2：
输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]
示例 3：
输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]
示例 4：
输入：head = []
输出：[]
解释：给定的链表为空（空指针），因此返回 null。
分析题目可知，这里要求的复制链表并不是我们常常所说的链表元素复制，因为它不仅涉及了next指针还涉及到了另一个指针random，所以它是一种深拷贝。
这里要区别一下深拷贝和浅拷贝区别：浅拷贝只复制指向某个对象的指针，而不复制对象本身，复制前后的对象依旧是共享同一内存块，但深拷贝会类似于我们所说的复制粘贴操作，它额外创造一个新对象并将旧对象复制给新对象，新对象跟原对象不共用同一内存块，修改新对象并不会改到原对象。
思路1：复制链表并拆分。直接在原链表基础上复制新链表，即让原节点next指向自己的拷贝节点，然后拆分random， 拷贝节点的random指向其指向的原节点的next，最后，再拆next，让其每一个节点next都指向其原来指向的下一节点，文字描述有点晦涩，直接上图(图中合并部分，即拷贝过程中，由于空间有限，没有画出原有链表的random指向，其实原有链表的指向和拷贝之前的一样)
思路2：使用哈希表map表示映射关系，其中哈希表的键值key是原节点，value值是复制的新节点。具体流程可以分为二步，第一步是遍历原链表，利用哈希表映射新节点和旧节点关系，即每遍历一个节点，则复制一个val值相同的新节点，mp[p]= new Node(p->val)。第二步是遍历map，复制next和random指针的对应关系，并更新新节点的next和random所指的值，最后返回新链表的头节点即可，即即mp[p]->next=mp[p->next]和mp[p]->random=mp[p->random]。
思路3：在使用哈希表的基础上，用DFS优化程序
合并+拆分
/* // Definition for a Node. class Node { public: int val; Node* next; Node* random; Node(int _val) { val = _val; next = NULL; random = NULL; } }; */ class Solution { public: Node* copyRandomList(Node* head) { if(head == nullptr) return nullptr; Node* newHead = head; while(newHead) { Node* p = new Node(newHead->val); Node* q = newHead->next; newHead->next = p; p->next = q; newHead = p->next; } newHead=head//头节点 while(newHead) { if(newHead->random) newHead->next->random=newHead->random->next; newHead=newHead->next->next; } newHead = head; Node* t = head->next; Node* pHead = head->next; while(newHead) { newHead->next = newHead->next->next; newHead = newHead->next; if(t->next) { t->next = t->next->next; t = t->next; } } return pHead; } };
哈希表
/* // Definition for a Node. class Node { public: int val; Node* next; Node* random; Node(int _val) { val = _val; next = NULL; random = NULL; } }; */ class Solution { public: Node* copyRandomList(Node* head) { if(head == nullptr) return nullptr; unordered_map<Node*, Node*> mp; Node* p = head; while(p) { mp[p] = new Node(p->val); p = p->next; } p = head; while(p) { if(p->next != nullptr) { mp[p]->next = mp[p->next]; } if(p->random != nullptr) { mp[p]->random = mp[p->random]; } p = p->next; } return mp[head]; };
哈希+DFS
/* // Definition for a Node. class Node { public: int val; Node* next; Node* random; Node(int _val) { val = _val; next = NULL; random = NULL; } }; */ class Solution { public: Node* copyRandomList(Node* head) { unordered_map<Node*, Node*> mp; dfs(head, mp); return mp[head]; } Node* dfs(Node* head, unordered_map<Node*, Node*> &mp) { if(head == nullptr) return nullptr; if(mp.count(head)) return mp[head]; mp[head] = new Node(head->val); mp[head]->next = dfs(head->next, mp); mp[head]->random = dfs(head->random, mp); return mp[head]; } };
原文：https://www.cnblogs.com/wzw0625/p/12682294.html