取名字网站如何做北京广告公司

138. 复制带随机指针的链表 - 力扣（LeetCode）

深拷贝类似：LeetCode第 133 题：克隆图(C++)_zj-CSDN博客

不过这题思想简单很多：

使用哈希表映射：

class Solution {
public:Node* copyRandomList(Node* head) {if(!head)   return head;unordered_map<Node*, Node*> m;//<原节点，深拷贝节点>for(Node* cur = head; cur != NULL; cur = cur->next)m[cur] = new Node(cur->val);//新建节点//将新建的节点按照原来的映射关系组织成链表for(Node* cur = head; cur != NULL; cur = cur->next){m[cur]->next = m[cur->next];m[cur]->random = m[cur->random];}return m[head];}
};

dfs:

class Solution {
public:unordered_map<Node*, Node*> m;Node* copyRandomList(Node* head) {return dfs(head);}Node* dfs(Node *head){if(!head)   return NULL;if(m.count(head))   return m[head];auto cur = new Node(head->val);m[head] = cur;cur->next = dfs(head->next);cur->random = dfs(head->random);return cur;}
};

看别人的题解还有更好的方法：直接在链表上进行克隆：复杂链表的复制-（看了绝对秒懂的思路）简单易懂的三步解决问题 - 复杂链表的复制 - 力扣（LeetCode）

/*
// 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)   return head;auto cur = head;while(cur){//复制链表节点auto copy = new Node(cur->val);copy->next = cur->next;cur->next = copy;cur = cur->next->next;}cur = head;while(cur){//调整随机指针的指向//此时节点已经复制过了//cur的next是cur的拷贝, cur->random->next也是cur->random的拷贝if(cur->random) cur->next->random = cur->random->next;cur = cur->next->next;}auto copyhead = head->next;cur = head;auto curcopy = head->next;while(cur){cur->next = cur->next->next;cur = cur->next;if(curcopy->next){curcopy->next = curcopy->next->next;curcopy = curcopy->next;}}return copyhead;}
};