1)第一次遍历构建完整节点
map.put(cur,newNode);
2)第二次遍历填充它的random指针和next指针
1、 找Y 对应Key—value map.get(X)在
2、在value中设置这个节点的next,和random指针
a) 找指向X 在原链表中查找Y（7）的next值X（13）
b) 找X对应key—value 通过原链表map.get(X)在value中寻找对应的X
c) 连接，在value中将Y（7）.next=map.get(X)
class Solution {
public Node copyRandomList(Node head) {
//边界判断，一般链表的题目都需要判断头节点是否为空
//从链表的头节点开始遍历
//使用一一对应的哈希表结构 Map 存放已经创建的节点
//1遍历原链表
//以原链表的节点为 Key ,创建一个 Map
//Map 的 Value 为一个新链表中的节点
//新节点的值 Val 和原链表的值 Val 一样
//但愿链表中的每个节点都有 next 和 random 指针，而 Map 中的 Value 没有 next 和 random 指针
//map.put(key,value)
//查看下一个节点的情况
//2再次从链表的头节点开始遍历
//遍历原链表
//原链表节点--- 新链表节点
//key --- Value
//cur --- map.get(cur)
//0、在字典中找到一个 cur 为 key 对应的那个 value 值
//接下来，需要去寻找 valueCur 的 next 节点 和 random 节点
//寻找 valueCur 的 next 节点
//1。获取当前节点 cur 在原链表中的 next 指针指向的节点
//2、在字典中找到以 keyNextNode 为 key 对应的那个 value 值
//3、那么新联表中的这个节点的 next 指针就是 valueNextNode
//寻找 valueCur 的节点
//1、获取当前节点 cur 在原链表中的 random 指针指向的节点
//2、在在字典中找到以 valueRandomNode 为 key 对应的那个 value 值
//3、那么新链表中的这个节点的 next 指针就是 valueNextNode
//遍历下去，查看下一个节点
}
// 原链表节点 --- 新链表节点
// key --- value
// cur --- map.value(cur)
// head --- map.get(head)
}
class Solution {
public Node copyRandomList(Node head) {
//边界判断，一般链表的题目都需要判断头节点是否为空
if(head == null ) return null;
//从链表的头节点开始遍历
Node cur = head;
//使用一一对应的哈希表结构 Map 存放已经创建的节点
Map map = new HashMap<>();
//1遍历原链表:创建
while( cur != null){
//以原链表的节点为 Key ,创建一个 Map
//Map 的 Value 为一个新链表中的节点
//新节点的值 Val 和原链表的值 Val 一样
//但愿链表中的每个节点都有 next 和 random 指针，而 Map 中的 Value 没有 next 和 random 指针
//map.put(key,value)
Node newNode = new Node(cur.val);
//查看下一个节点的情况
map.put(cur,newNode);
cur = cur.next;
}
//2再次从链表的头节点开始遍历:next和random指针
cur = head;
//遍历原链表
while( cur != null){
//原链表节点--- 新链表节点
//key --- Value
//cur --- map.get(cur)
//0、找Y： 在字典中找到一个 cur 为 key 对应的 那个 value 值
Node valueCur = map.get(cur);
//接下来，需要去寻找 valueCur 的 next 节点 和 random 节点
//寻找 valueCur 的 next 节点
//1。获取当前节点 cur 在原链表中的 next 指针 指向 的节点
Node keyNextNode = cur.next;
//2、在字典中找到以 keyNextNode 为 key 对应的那个 value 值
Node valueNextNode = map.get(keyNextNode);
//3、那么新联表中的这个节点的 next 指针就是 valueNextNode
valueCur.next = valueNextNode;
//寻找 valueCur 的random节点
//1、获取当前节点 cur 在原链表中的 random 指针指向的节点
Node keyRandomNode = cur.random;
//2、在在字典中找到以 valueRandomNode 为 key 对应的那个 value 值
Node valueRandomNode = map.get(keyRandomNode);
//3、那么新链表中的这个节点的 next 指针就是 valueNextNode
valueCur.random = valueRandomNode;
//遍历下去，查看下一个节点
cur = cur.next;
}
// 原链表节点 --- 新链表节点
// key --- value
// cur --- map.value(cur)
// head --- map.get(head)
return map.get(head);
}
}
