剑指 Offer 35. 复杂链表的复制

题意：请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

解题思路

解法：
1.分析题意，本来链表遍历，即可得到链表的复制，但是此题的难点在于，在第一次遍历的时候，random很有可能还未遍历到，此时random指向的并非原链表的值
2.考虑到第一点，我们需要第一次遍历，构建链表，然后再次遍历next、random
3.由1、2可知，使用递归是最简单的做法
4.这里通过递归先完成next节点的创建，然后递归回来的时候，map已经记录好了，这个时候就直接使用map的value来设置random指针。所以headNew.random = copyRandomList(head.random);可以改成headNew.random = cachedNode.get(head.random); 这样更加容易理解。

解题遇到的问题

无

后续需要总结学习的知识点

无

##解法1
class Solution {
    Map<Node, Node> cachedNode = new HashMap<Node, Node>();

    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }

        if (!cachedNode.containsKey(head)) {
            Node headNew = new Node(head.val);
            cachedNode.put(head, headNew);
            headNew.next = copyRandomList(head.next);
            headNew.random = copyRandomList(head.random);
        }
        return cachedNode.get(head);
    }
}
/*
// 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;
    }
}
*/