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

  • 2
    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

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

  • 0

    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.