力扣

题意

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点（可以指向自己）或者 null。

题目意思：你根本不知道这个链表具体长什么样子，你只能通过遍历这个链表来得到它的信息，来推它是长什么样，（示例的图其实你是看不见的），推完之后，你就得到（和示例那些图 ）结构一样的链表了。

法1—哈希表

利用哈希表的查询特点，考虑构建 原链表节点 和 新链表对应节点 的键值对映射关系，再遍历构建新链表各节点的 next 和 random 引用指向即可。

算法流程：

1. 若头节点 head 为空节点，直接返回 nullptr ；
2. 初始化： 哈希表 dic ， 节点 cur 指向头节点；
3. 复制链表：
   1. 建立新节点，并向 dic 添加键值对 (原 cur 节点, 新 cur 节点） ；
   2. cur 遍历至原链表下一节点；
4. 构建新链表的引用指向：
   1. 构建新节点的 next 和 random 引用指向；
   2. cur 遍历至原链表下一节点；
5. 返回值： 新链表的头节点 dic[cur] ；

C++实现

/*// 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)     { // 1、若头结点为空，直接返回nullptr if(nullptr==head)     return nullptr; // 2、初始化哈希表和指针cur unordered_map dic; Node* cur = head; // 3、复制链表，并且建立 “原cur节点 —> 新cur节点” 的Map映射 while(nullptr!=cur) {     dic[cur] = new Node(cur->val);     cur=cur->next; } cur = head; // 恢复cur的指向，使其指向头结点 // 4、构建新链表的 next指向和random指向 while(nullptr!=cur) {     dic[cur]->next = dic[cur->next];     dic[cur]->random = dic[cur->random];     /*     需要注意的是，这里 dic[cur]->next != cur->next。     dic[cur]表示新的链表结点，它的next只能指向 自己新的链表中的节点，而不能指向旧链表中的节点。     */     cur = cur->next; } // 5、返回新链表的头结点 return dic[head];    }};

 法2—拼接+拆分

考虑构建  原节点 1 -> 新节点 1 -> 原节点 2 -> 新节点 2 -> ……  的拼接链表，如此便可在访问原节点的 random 指向的节点 的同时找到新对应新节点的 random 指向的节点。

 算法流程：

1. 复制各节点，构建拼接链表 
   • 设原链表为 node1→node2 → ⋯ ，构建的拼接链表如下所示：
   •  
2. 构建新链表各节点的 random 指向：
   • 当访问原节点 cur 的随机指向节点 cur.random 时，对应新节点 cur.next 的随机指向节点为 cur.random.next 。
3. 拆分原 / 新链表：

   • 设置 pre / cur 分别指向 原 / 新链表头节点，遍历执行 pre.next = pre.next.next 和 cur.next = cur.next.next 将两链表拆分。

4. 返回新链表的头节点 res 即可

C++实现

/*// 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)     { // 若头结点为空，直接返回nullptr if(nullptr==head)     return nullptr; // 1、复制各节点，构建拼接链表 // node1->node1_new->node2->node2_new->...noden->noden_new->NULL Node* cur = head; while(nullptr!=cur) {     Node* temp = new Node(cur->val); //创建新节点     temp->next = cur->next; // 新节点的next指向原节点的next     cur->next = temp;   //原节点的next指向新节点     cur = temp->next; // cur指向原链表的下一个节点 } // 2、构建新链表各节点的 random 指向 cur = head; while(nullptr!=cur) {     if(cur->random!=nullptr)     {  //如果cur的random指向空，则 cur对应的新节点 cur->next 的random也要指向空  //但是在创建新链表的时候，默认新链表的random全都是空，所以没必要处理 新节点的  // randm为空的情况。所以必须要进行这一步的判断，否则还会引起bug cur->next->random = cur->random->next;     }     cur = cur->next->next; } // 3、拆分原/新链表 Node* pre=head; //pre指向原链表头 cur = head->next;   //cur指向新链表头 Node* new_head = cur;// 先把新链表头保存下来 while(cur->next!=nullptr) {     pre->next = pre->next->next;     cur->next = cur->next->next;     pre = pre->next;     cur = cur->next; } // 当跳出while循环时，表示cur已经到达了新链表的最后一个节点，因为新链表最后一个节点的 // next指向空。此时要单独处理原链表的最后一个节点的next指向。 pre->next = nullptr; // 4、返回新链表的头结点即可 return new_head;    }};

闲鱼礼物网