14 lines java solution, use o(n) space, is there a solution without extra space?


  • 2
    M
    HashMap<Integer, UndirectedGraphNode> cache = new HashMap<Integer, UndirectedGraphNode>();
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        if (node == null) return null;
        UndirectedGraphNode curr = new UndirectedGraphNode(node.label);
        cache.put(curr.label, curr);
        for (UndirectedGraphNode ugn : node.neighbors) {
            if (ugn.label == curr.label) curr.neighbors.add(curr); // self loop
            else {
                if (cache.containsKey(ugn.label)) curr.neighbors.add(cache.get(ugn.label));
                else curr.neighbors.add(cloneGraph(ugn));
            }
        }
        return curr;
    }

  • 2
    V

    I don't think you need to check the self loop. good luck.


  • 0
    K

    The self-loop is covered by the following if (cache.containsKey(ugn.label)) check


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.