【leetcode】138 复制带随机指针的链表（链表）

题目链接：https://leetcode-cn.com/problems/copy-list-with-random-pointer/

题目描述

给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。

要求返回这个链表的深拷贝。

示例：

输入： {"$id":"1","next":{"$id":"2","next":null,"random":{"$ref":"2"},"val":2},"random":{"$ref":"2"},"val":1} 解释： 节点 1 的值是 1，它的下一个指针和随机指针都指向节点 2 。 节点 2 的值是 2，它的下一个指针指向 null，随机指针指向它自己。

提示：

你必须返回给定头的拷贝作为对克隆列表的引用。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/copy-list-with-random-pointer 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

1 哈希表

/* * 哈希表存储原链表节点到复制链表节点的映射 * 时间复杂度：O(n) 空间复杂度：O(n) */ class Solution { public: Node* copyRandomList(Node* head) { if(!head) return nullptr; Node *pNode = head; unordered_map<Node*,Node*> m; // 复制链表节点并建立映射 while(pNode){ Node *copyNode = new Node(pNode->val, nullptr, nullptr); m[pNode] = copyNode; pNode = pNode->next; } // 设置指针 pNode = head; while (pNode){ m[pNode]->next = m[pNode->next]; m[pNode]->random = m[pNode->random]; pNode = pNode->next; } return m[head]; } };

2 原链表上操作

/* * 在原链表节点后复制新节点 * （1）复制链表节点 * （2）设置随机指针 * （3）分割链表 * 时间复杂度：O(n) 空间复杂度：O(1) */ class Solution { public: Node* copyRandomList(Node* head) { if(!head) return nullptr; Node *pNode = head; Node *pNext = nullptr; // 复制链表节点 while(pNode){ pNext = pNode->next; pNode->next = new Node(pNode->val, nullptr, nullptr); pNode->next->next = pNext; pNode = pNext; } // 设置随机指针 pNode = head; Node *pCopy = nullptr; while (pNode){ pCopy = pNode->next; pCopy->random = pNode->random->next; pNode = pNode->next->next; } // 分割链表 调整next指针 pNode = head; Node *copyHead = head->next; while (pNode){ pNext = pNode->next->next; pCopy = pNode->next; pNode->next = pNext; // 原链表 pCopy->next = pNext != nullptr ? pNext->next : nullptr; // 复制链表 pNode = pNext; } return copyHead; } };