LeetCode 138题解 | 随机链表的复制
随机链表的复制
- 一、题目链接
- 二、题目
- 三、分析
- 四、代码
一、题目链接
138.随机链表的复制
二、题目
三、分析
数据结构初阶阶段,为了控制随机指针,我们将拷贝结点链接在原节点的后面解决,后面拷贝节点还得解下来链接,非常麻烦。这里我们直接让{原结点,拷贝结点}建立映射关系放到map中,控制随机指针会非常简单方便,这里体现了map在解决一些问题时的价值,完全是降维打击。
深拷贝一遍原链表,并连接。确定拷贝结点的random指针就需要原结点找到对应的拷贝结点:map< 原结点,拷贝结点>。
四、代码
/*
// 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) {map<Node*, Node*> nodeMap;Node* copyhead = nullptr, *copytail = nullptr;Node* cur = head;while (cur){Node* copy = new Node(cur->val);if (copytail == nullptr){copyhead = copytail = copy;}else{copytail->next = copy;copytail = copy;}nodeMap.insert({ cur, copy });// 或者 nodeMap[cur] = copytail;cur = cur->next;}cur = head;Node* copy = copyhead;while (cur){if (cur->random == nullptr){copy->random = nullptr;}else{copy->random = nodeMap[cur->random];}cur = cur->next;copy = copy->next;}return copyhead;}
};