原题（来源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/
相关推荐
-
leetcode24-两两交换链表中的节点
原题 给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。 示例: 给定 1->2->3->...
-
leetcode376-摆动序列
原题 如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。少于两个元素的序列也是摆动序列。 例如， [1,7,4,9,...
-
leetcode239-滑动窗口最大值
原题 给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。 返回滑动窗口中的最...
-
leetcode1-两数之和
原题 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是，你不能...
-
leetcode108-将有序数组转换为二叉搜索树
原题 将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。 本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。 示例: 给定有序数...
-
leetcode217-存在重复元素
原题 给定一个整数数组，判断是否存在重复元素。 如果任何值在数组中出现至少两次，函数返回 true。如果数组中每个元素都不相同，则返回 false。 示例1： 输入： [1,2,3...
-
leetcode73-矩阵置零
原题 给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法。 示例 1: 输入: [ [1,1,1], ...
-
leetcode123-买卖股票的最佳时机III
原题 给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。 注意: 你不能同时参与多笔交易（你...
-
leetcode38-外观数列
原题 「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。前五项如下： 1. 1 2. 11 3. 21 4. 1211 5. 111221 1 被读作...
-
leetcode151-翻转字符串里的单词
原题 给定一个字符串，逐个翻转字符串中的每个单词。 示例 1: 输入: “the sky is blue” 输出: “blue is sky the” 示例 2: 输入: “ he...