class Solution {
public Node copyRandomList(Node head) {
if(head == null){
return null;
}
//使cur指向原链表的头节点
Node cur = head;
//创建哈希表
//<原链表节点, 新的链表节点>
Map<Node, Node> map = new HashMap<>();
while(cur != null){
//建立新的节点
Node node = new Node(cur.val);
//向哈希表中添加键值对(原cur节点, 新cur节点)
map.put(cur, node);
//更新cur, 继续往后遍历
cur = cur.next;
}
//cur指向原链表的头节点
cur = head;
while(cur != null){
//构建新链表的 next 和 random 指向
//map.get(cur).next ==> node.next
//map.get(cur.next) ==> 获取到cur.next对应的新节点
map.get(cur).next = map.get(cur.next);
//random同理
map.get(cur).random = map.get(cur.random);
cur = cur.next;
}
//返回新链表的头节点
return map.get(head);
}
}
