原题(来源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 <= 10000
Node.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/