请实现 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 。
其实这道题就是要将链表深拷贝并获取
利用HashMap来存储节点，key是当前的节点，value代表实际的节点（拷贝之后的）
如图所示，表示如何复制节点以及复制指向
class Solution {
public Node copyRandomList(Node head) {
HashMap<Node, Node> hashMap = new HashMap<Node, Node>();
Node temp = head;
while (temp != null) {
//将当前节点作为key，构造新节点作为value 放入map中
hashMap.put(temp, new Node(temp.val));
//依次遍历
temp = temp.next;
}
//准备赋值引用
temp = head;
while (temp != null) {
hashMap.get(temp).next = hashMap.get(temp.next);
hashMap.get(temp).random = hashMap.get(temp.random);
temp = temp.next;
}
return hashMap.get(head);
}
}
本文地址：https://blog.csdn.net/qq_35416214/article/details/107542549
如对本文有疑问， 点击进行留言回复！！
网友评论