个人主页Milestone-里程碑❄️个人专栏: 力扣hot100 CLinuxGitMySQL心向往之行必能至【LeetCode 138】复制带随机指针的链表 C 超详细题解哈希表解法今天给大家分享一道经典的链表面试题 ——LeetCode 138. 复制带随机指针的链表这道题的核心难点在于随机指针的复制普通的链表深拷贝无法直接处理随机指向的关系我会用最易懂的思路结合 C 代码带大家一步步攻克它。题目描述给你一个长度为n的链表每个节点包含一个额外的随机指针random该指针可以指向链表中的任何节点或空节点。要求构造这个链表的深拷贝深拷贝应该完全由新节点组成任何原链表的指针都不能指向新节点最终返回新链表的头节点。节点结构定义如下cpp运行class Node { public: int val; Node* next; Node* random; Node(int _val) { val _val; next NULL; random NULL; } };解题思路这道题最直观、最容易理解的解法是哈希表法核心思想用哈希表建立原节点与新节点的映射关系分两步完成拷贝第一步遍历原链表仅拷贝节点值和 next 指针创建一条和原链表结构完全一样的新链表同时把「原节点新节点」的对应关系存入哈希表。第二步再次遍历原链表通过哈希表快速找到原节点的 random 指向的节点给新节点的 random 指针赋值。为什么要用哈希表因为随机指针random可以指向任意节点在第一次拷贝时新节点的 random 指向的节点可能还没创建无法直接赋值。用哈希表存储原节点 → 新节点的映射后只要知道原节点的 random 指向谁就能直接查到对应的新节点完美解决随机指针的拷贝问题。容器选择map 与 unordered_map 对比代码中我用了map也可以替换为unordered_map两者效率差异很大map底层红黑树查找时间复杂度O(logn)unordered_map底层哈希表查找时间复杂度O(1)在本题中m[cur-random]是核心查找操作推荐用 unordered_map 提升效率。完整代码实现cpp运行/* // 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; // 哈希表key 原链表节点value 新链表对应节点 unordered_mapNode*, Node* m; Node* newHead nullptr; // 新链表头节点 Node* newTail nullptr; // 新链表尾节点用于尾插 Node* cur head; // 遍历原链表的指针 // 第一步遍历原链表拷贝值和next指针建立映射关系 while(cur) { if(newTail nullptr) // 第一个节点头节点和尾节点指向同一个新节点 newHead newTail new Node(cur-val); else{ // 非第一个节点尾插法添加新节点 newTail-next new Node(cur-val); newTail newTail-next; } // 存储原节点与拷贝节点的映射为random拷贝做准备 m[cur] newTail; cur cur-next; } // 第二步再次遍历原链表拷贝random指针 cur head; // 重置指针重新遍历原链表 Node* nCur newHead; // 遍历新链表的指针 while(cur) { // 原节点random为空新节点也置空 if(cur-random nullptr) nCur-random nullptr; else{ // 通过哈希表找到原节点random对应的新节点 nCur-random m[cur-random]; } nCur nCur-next; cur cur-next; } // 返回新链表的头节点 return newHead; } };代码逐段解析1. 边界判断cpp运行if(head nullptr) return nullptr;如果原链表为空直接返回空避免空指针访问。2. 哈希表初始化cpp运行unordered_mapNode*, Node* m;创建哈希表存储原节点和新节点的一一对应关系。3. 第一步拷贝值与 next 指针用尾插法创建新链表保证顺序和原链表一致每创建一个新节点就把原节点:新节点存入哈希表遍历完成后新链表的next结构完全拷贝完成。4. 第二步拷贝 random 指针重新同时遍历原链表和新链表原节点的random指向谁就通过哈希表找到对应的新节点赋值给新节点的random完美解决随机指针的拷贝问题。复杂度分析时间复杂度O (n)仅遍历两次链表哈希表查找为 O (1)空间复杂度O (n)需要哈希表存储 n 个节点的映射关系。进阶本题还有原地修改链表的 O (1) 空间解法不需要哈希表思路是把新节点插入到原节点后面再分离链表后续我会单独出一篇进阶解法的博客总结这道题是链表深拷贝的经典变形哈希表法是最适合新手的解法核心就是用映射关系解决随机指针的指向问题逻辑清晰、代码易写面试中能快速上手。我是爱编程的程序员持续分享 LeetCode 题解、C 知识点欢迎关注交流总结本题核心难点是随机指针的深拷贝哈希表法是最易懂的解法分两步操作先拷贝值和 next再通过哈希表拷贝 random推荐使用unordered_map查找效率更高整体时间复杂度 O (n)代码边界判断、尾插法、哈希映射是关键细节面试中一定要注意。
链表--随机链表的复制
个人主页Milestone-里程碑❄️个人专栏: 力扣hot100 CLinuxGitMySQL心向往之行必能至【LeetCode 138】复制带随机指针的链表 C 超详细题解哈希表解法今天给大家分享一道经典的链表面试题 ——LeetCode 138. 复制带随机指针的链表这道题的核心难点在于随机指针的复制普通的链表深拷贝无法直接处理随机指向的关系我会用最易懂的思路结合 C 代码带大家一步步攻克它。题目描述给你一个长度为n的链表每个节点包含一个额外的随机指针random该指针可以指向链表中的任何节点或空节点。要求构造这个链表的深拷贝深拷贝应该完全由新节点组成任何原链表的指针都不能指向新节点最终返回新链表的头节点。节点结构定义如下cpp运行class Node { public: int val; Node* next; Node* random; Node(int _val) { val _val; next NULL; random NULL; } };解题思路这道题最直观、最容易理解的解法是哈希表法核心思想用哈希表建立原节点与新节点的映射关系分两步完成拷贝第一步遍历原链表仅拷贝节点值和 next 指针创建一条和原链表结构完全一样的新链表同时把「原节点新节点」的对应关系存入哈希表。第二步再次遍历原链表通过哈希表快速找到原节点的 random 指向的节点给新节点的 random 指针赋值。为什么要用哈希表因为随机指针random可以指向任意节点在第一次拷贝时新节点的 random 指向的节点可能还没创建无法直接赋值。用哈希表存储原节点 → 新节点的映射后只要知道原节点的 random 指向谁就能直接查到对应的新节点完美解决随机指针的拷贝问题。容器选择map 与 unordered_map 对比代码中我用了map也可以替换为unordered_map两者效率差异很大map底层红黑树查找时间复杂度O(logn)unordered_map底层哈希表查找时间复杂度O(1)在本题中m[cur-random]是核心查找操作推荐用 unordered_map 提升效率。完整代码实现cpp运行/* // 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; // 哈希表key 原链表节点value 新链表对应节点 unordered_mapNode*, Node* m; Node* newHead nullptr; // 新链表头节点 Node* newTail nullptr; // 新链表尾节点用于尾插 Node* cur head; // 遍历原链表的指针 // 第一步遍历原链表拷贝值和next指针建立映射关系 while(cur) { if(newTail nullptr) // 第一个节点头节点和尾节点指向同一个新节点 newHead newTail new Node(cur-val); else{ // 非第一个节点尾插法添加新节点 newTail-next new Node(cur-val); newTail newTail-next; } // 存储原节点与拷贝节点的映射为random拷贝做准备 m[cur] newTail; cur cur-next; } // 第二步再次遍历原链表拷贝random指针 cur head; // 重置指针重新遍历原链表 Node* nCur newHead; // 遍历新链表的指针 while(cur) { // 原节点random为空新节点也置空 if(cur-random nullptr) nCur-random nullptr; else{ // 通过哈希表找到原节点random对应的新节点 nCur-random m[cur-random]; } nCur nCur-next; cur cur-next; } // 返回新链表的头节点 return newHead; } };代码逐段解析1. 边界判断cpp运行if(head nullptr) return nullptr;如果原链表为空直接返回空避免空指针访问。2. 哈希表初始化cpp运行unordered_mapNode*, Node* m;创建哈希表存储原节点和新节点的一一对应关系。3. 第一步拷贝值与 next 指针用尾插法创建新链表保证顺序和原链表一致每创建一个新节点就把原节点:新节点存入哈希表遍历完成后新链表的next结构完全拷贝完成。4. 第二步拷贝 random 指针重新同时遍历原链表和新链表原节点的random指向谁就通过哈希表找到对应的新节点赋值给新节点的random完美解决随机指针的拷贝问题。复杂度分析时间复杂度O (n)仅遍历两次链表哈希表查找为 O (1)空间复杂度O (n)需要哈希表存储 n 个节点的映射关系。进阶本题还有原地修改链表的 O (1) 空间解法不需要哈希表思路是把新节点插入到原节点后面再分离链表后续我会单独出一篇进阶解法的博客总结这道题是链表深拷贝的经典变形哈希表法是最适合新手的解法核心就是用映射关系解决随机指针的指向问题逻辑清晰、代码易写面试中能快速上手。我是爱编程的程序员持续分享 LeetCode 题解、C 知识点欢迎关注交流总结本题核心难点是随机指针的深拷贝哈希表法是最易懂的解法分两步操作先拷贝值和 next再通过哈希表拷贝 random推荐使用unordered_map查找效率更高整体时间复杂度 O (n)代码边界判断、尾插法、哈希映射是关键细节面试中一定要注意。
