剑指 Offer 35. 复杂链表的复制 - leetcode 剑指offer系列
发布日期:2021-06-29 07:12:10
浏览次数:4
分类:技术文章
本文共 1530 字,大约阅读时间需要 5 分钟。
题目难度: 中等
今天继续更新剑指 offer 系列, 这道题实现起来并不难, 但需要一定的思考, 大家可以先尝试自己想想如何解决
老样子晚上 6 点 45 分准时更新公众号 每日精选算法题, 大家记得关注哦~ 另外在公众号里回复 offer 就能看到剑指 offer 系列当前连载的所有文章了
题目描述
请实现 copyRandomList 函数,复制一个复杂链表。在复杂链表中,每个节点除了有一个 next 指针指向下一个节点,还有一个 random 指针指向链表中的任意节点或者 null。
- -10000 <= Node.val <= 10000
- Node.random 为空(null)或指向链表中的节点。
- 节点数目不超过 1000 。
题目样例
示例
输入
head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出
[[7,null],[13,0],[11,4],[10,2],[1,0]]
题目思考
- 如何处理 random 指针?
解决方案
思路
- 如果只有 next 指针的话很简单, 我们只需要对每个节点新建一个相同值的节点, 并保持指向关系, 逐个遍历过去即可
- 现在多了个 random 指针, 想要定位新的指向的节点, 一个比较自然的想法就是额外维护一个老节点到新节点的映射关系, 可以用字典来实现
- 第一遍遍历, 就只关注 next 部分, 并建立好映射关系
- 第二遍遍历, 考虑 random 部分, 找到对应的新链表的节点, 然后当前节点的 random 指针指向它即可
复杂度
- 时间复杂度
O(N)
- 每个节点只需要遍历两次
- 空间复杂度
O(N)
- 额外需要一个字典
代码
class Solution: def copyRandomList(self, head: 'Node') -> 'Node': if not head: return None maps = { } # 第一遍遍历, 建立新的链表, 以及老节点到新节点的映射关系 copyHead = Node(head.val) origin, copy = head, copyHead maps[origin] = copy while origin.next: # 新建下一个节点, 并建立next关系 copy.next = Node(origin.next.val) origin = origin.next copy = copy.next maps[origin] = copy # 第二遍遍历, 处理random指针部分 origin, copy = head, copyHead while origin: if origin.random: # 如果老节点random指针指向非空的话, 就将当前新节点也指向随机节点对应的新节点 copy.random = maps[origin.random] origin = origin.next copy = copy.next return copyHead
大家可以在下面这些地方找到我~😊
我的公众号: 每日精选算法题, 欢迎大家扫码关注~😊
转载地址:https://blog.csdn.net/zjulyx1993/article/details/107470027 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
第一次来,支持一个
[***.219.124.196]2024年04月12日 00时06分37秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
4.27数学作业提示
2019-04-29
4.27数学练习册答案
2019-04-29
4.27语文答案
2019-04-29
4.29图二
2019-04-29
5.6语文笔记
2019-04-29
5.13数学练习册讲解
2019-04-29
5.15第三题答案
2019-04-29
六一征集作品
2019-04-29
5.22语文作业
2019-04-29
5.22数学作业答案
2019-04-29
unit 3 过关检测卷答案
2019-04-29
5.25数学作业答案
2019-04-29
5.25语文作业答案
2019-04-29
lesson22单词短语
2019-04-29
Docker学习(二):Docker基本操作(控制容器)
2019-04-29
鲲鹏HCIA认证之初识鲲鹏(二)
2019-04-29
主机安全运维检查方法
2021-07-02
windows安全运维
2021-07-02
勒索病毒解密工具
2021-07-02
使用npm构建项目,码云+git管理代码(小白教程)
2021-07-02