LeetCode程序员面试金典：克隆图

题目：

在无向连接图中引用一个节点，请返回图中的深拷贝(克隆)。

图中的每个节点都包含其值 val（int） 列表及其邻居（list[Node]）。

class Node {

public int val;

public List<Node> neighbors;

}

测试用例格式：

简单来说，每个节点的值都和它的索引一样。例如，第一个节点值是 1（val = 1)第二个节点值为 2（val = 2)，以此类推。在测试用例中使用相邻列表表示此图。

邻接列表 无序列表的集合是用来表示有限图的。每个列表都描述了图中节点的邻居集。

给定节点将永远是图中的第一个节点(值为 1)。您必须将给定节点的副本作为对克隆图的引用返回。

示例 1：

输入：adjList = [2，4]，[1，3]，[2，4]，[1，3]

输出:[2，4]，[1，3]，[2，4]，[1，3]

解释：

图中有 4 个节点。

节点 1 的值是 1.它有两个邻居：节点 2 和 4 。

节点 2 的值是 2.它有两个邻居：节点 1 和 3 。

节点 3 的值是 3.它有两个邻居：节点 2 和 4 。

节点 4 的值是 4.它有两个邻居：节点 1 和 3 。

示例 2：

输入：adjList = [[]]

输出：[[]]

说明:输入包含一个空列表。这张图只有一个值 1 没有邻居的节点。

示例 3：

输入：adjList = []

输出：[]

说明:这张图是空的，不含任何节点。

示例 4：

输入：adjList = [2]，[1]]

输出：[2]，[1]]

代码实现：

class Solution {    private HashMap <Node, Node> visited = new HashMap <> ();    public Node cloneGraph(Node node) {        if (node == null) {            return node;        }        // 若该节点已被访问，直接从哈希表中取出相应的克隆节点返回        if (visited.containsKey(node)) {            return visited.get(node);        }        // 克隆节点，注意到我们不会为了深度复制而克隆邻居的列表        Node cloneNode = new Node(node.val, new ArrayList());        // 哈希表存储        visited.put(node, cloneNode);        // 遍历节点的邻居，更新克隆节点的邻居列表        for (Node neighbor: node.neighbors) {            cloneNode.neighbors.add(cloneGraph(neighbor));        }        return cloneNode;    }}