138. 随机链表的复制

leetcodehttps://leetcode.cn/problems/copy-list-with-random-pointer/description/?envType=study-plan-v2&envId=top-interview-150

解题思路

一边遍历一边新建节点，用哈希表记录哪些节点已经创建过。如果创建过直接返回，否则新建节点。注意哈希表更新须在递归遍历前面，否则死循环。

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/

class Solution {
    HashMap<Node,Node>mp=new HashMap<>();
    Node copy(Node head){
        if(head==null){
            return null;
        }
        Node node;
        if(mp.get(head)==null){
            node=new Node(head.val);
        }
        else{
            return mp.get(head);
        }
        mp.put(head,node);//   必须在递归前面
        node.next=copy(head.next);
        node.random=copy(head.random);
        return node;
    }
    public Node copyRandomList(Node head) {
        return copy(head);
    }
}