复制带随机指针的链表
题目链接: https://leetcode.cn/problems/copy-list-with-random-pointer
解题思路:
遍历链表,对每个节点,从cache中查找,若不存在则构建新节点,并存储到cache中,若存在则从cache中直接读取
对于Random的节点,从cache中查找,若cache中不存在Random节点,则构建Random节点,并存储到cache中
复杂度分析
最后更新于
这有帮助吗?
题目链接: https://leetcode.cn/problems/copy-list-with-random-pointer
遍历链表,对每个节点,从cache中查找,若不存在则构建新节点,并存储到cache中,若存在则从cache中直接读取
对于Random的节点,从cache中查找,若cache中不存在Random节点,则构建Random节点,并存储到cache中
最后更新于
这有帮助吗?
时间复杂度: 只遍历了一遍链表,因此时间复杂度为 ,其中 是链表的长度
空间复杂度: 空间复杂度为