原题（来源Leetcode）
请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
示例 1:
输入: head = [[7,null],[13,0],[11,4],[10,2],[1,0]] 输出: [[7,null],[13,0],[11,4],[10,2],[1,0]]
示例 2:
输入: head = [[1,1],[2,1]] 输出: [[1,1],[2,1]]
示例 3:
输入： head = [[3,null],[3,0],[3,null]] 输出： [[3,null],[3,0],[3,null]]
示例 4：
输入： head = [] 输出： [] 解释： 给定的链表为空（空指针），因此返回 null。
提示:
-10000 <= Node.val <= 10000Node.random为空（null）或指向链表中的节点。- 节点数目不超过 1000 。
注意： 本题与主站 138 题相同：https://leetcode-cn.com/problems/copy-list-with-random-pointer/
解法
思想
我第一个想到的居然是Spring IOC解决循环依赖的思想。。先扫描一遍把节点都缓存下来，并用HashMap记录新旧节点的对应关系，然后再扫描一遍设置random节点。
代码
class Solution {
public Node copyRandomList(Node head) {
Map<Node,Node> map = new HashMap<>();
Node sentinel = new Node(0);
Node curOld = head;
Node curNew = sentinel;
while(curOld!=null ){
Node copy = new Node(curOld.val);
curNew.next = copy;
curNew = copy;
map.put(curOld,copy);
curOld = curOld.next;
}
for(Map.Entry<Node,Node> entry:map.entrySet()){
Node old = entry.getKey();
if(old.random != null)
map.get(old).random = map.get(old.random);
}
return sentinel.next;
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/%e5%89%91%e6%8c%87offer35-%e5%a4%8d%e6%9d%82%e9%93%be%e8%a1%a8%e7%9a%84%e5%a4%8d%e5%88%b6/
相关推荐
-
leetcode19-删除链表的倒数第N个节点
原题 给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。 示例: 给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除了倒数第二个节点后，链表变为...
-
leetcode349-两个数组的交集
原题 给定两个数组，编写一个函数来计算它们的交集。 输入： nums1 = [1,2,2,1], nums2 = [2,2] 输出： [2] 示例2： 输入： nums1 = [4...
-
leetcode169-多数元素
原题 给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的，并且给定的数组总是存在多数元素。 示例1:...
-
leetcode96-不同的二叉搜索树
原题 给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？ 示例: 输入: 3 输出: 5 解释: 给定 n = 3, 一共有 5 种不同结构的二叉搜索树: &...
-
leetcode124-二叉树中的最大路径和
原题 给定一个非空二叉树，返回其最大路径和。 本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。 示例 1: 输入: [1...
-
leetcode974-和可被K整除的子数组
原题 给定一个整数数组 A，返回其中元素之和可被 K 整除的（连续、非空）子数组的数目。 示例: 输入： A = [4,5,0,-2,-3,1], K = 5 输出： 7 解释： ...
-
leetcode110-平衡二叉树
原题 给定一个二叉树，判断它是否是高度平衡的二叉树。 本题中，一棵高度平衡二叉树定义为： 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。 示例 1: 给定二叉树 [...
-
leetcode105-从前序与中序遍历序列构造二叉树
原题 根据一棵树的前序遍历与中序遍历构造二叉树。 注意:你可以假设树中没有重复的元素。 例如，给出 前序遍历 preorder = [3,9,20,15,7] 中序遍历 inord...
-
leetcode559-N叉树的最大深度
原题 给定一个 N 叉树，找到其最大深度。 最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。 例如，给定一个 3叉树 : 我们应返回其最大深度，3。 说明: 树的深度不会...
-
leetcode572-另一个树的子树
原题 给定两个非空二叉树 s 和 t，检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树...