原题（来源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/
