/* // Definition for a Node. class Node { public int val; public List<Node> neighbors; public Node() { val = 0; neighbors = new ArrayList<Node>(); } public Node(int _val) { val = _val; neighbors = new ArrayList<Node>(); } public Node(int _val, ArrayList<Node> _neighbors) { val = _val; neighbors = _neighbors; } } */ class Solution { public Node cloneGraph(Node node) { if(node==null){ return null; } Map<Node,Node> map=new HashMap<Node,Node>(); ArrayList<Node> nodes=getNodes(node); //copy node for(Node n:nodes){ map.put(n,new Node(n.val)); } //copy neighbors for(Node n:nodes){ Node newNode=map.get(n); for(Node neighbor:n.neighbors){ Node newNeighbor=map.get(neighbor); newNode.neighbors.add(newNeighbor); } } return map.get(node); } public ArrayList<Node> getNodes(Node node){ //这里使用队列queue和set实现链表 Queue<Node> queue=new LinkedList<Node>(); HashSet<Node> set=new HashSet<Node>(); queue.add(node); set.add(node); while(!queue.isEmpty()){ Node head=queue.poll(); for(Node neighbor:head.neighbors){ if(!set.contains(neighbor)){ set.add(neighbor); queue.add(neighbor); } } } return new ArrayList(set); } }