[数据结构与算法]2021-10-16 35.复杂链表的复制-----HashMap

解题思路

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<Node,Node> 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);
    }
}