My java solution with O(n) time without hash map


  • -6
    N

    I assume that in the input graph, the neighbors of each node and the elements in them will NOT be null.

    public class Solution {
        private void f1(UndirectedGraphNode n) {
            List<UndirectedGraphNode> nb = n.neighbors;
            if (nb == null || nb.size() > 0 && nb.get(nb.size() - 1).neighbors == null) {
                return;
            }
            UndirectedGraphNode copy = new UndirectedGraphNode(n.label);
            copy.neighbors = null;
            nb.add(copy);
            for (UndirectedGraphNode n2 : nb) {
                f1(n2);
            }
        }
        private void f2(UndirectedGraphNode n) {
            List<UndirectedGraphNode> nb = n.neighbors;
            UndirectedGraphNode copy = nb.get(nb.size() - 1);
            if (copy.neighbors != null) {
                return;
            }
            copy.neighbors = new ArrayList<>();
            for (int i = 0; i < nb.size() - 1; i++) {
                UndirectedGraphNode n2 = nb.get(i);
                List<UndirectedGraphNode> nb2 = n2.neighbors;
                copy.neighbors.add(nb2.get(nb2.size() - 1));
                f2(n2);
            }
            copy.neighbors.add(null);
        }
        private void f3(UndirectedGraphNode n) {
            List<UndirectedGraphNode> nb = n.neighbors;
            if (nb.size() == 0) {
                return;
            }
            List<UndirectedGraphNode> nb2 = nb.get(nb.size() - 1).neighbors;
            if (nb2.size() == 0 || nb2.get(nb2.size() - 1) != null) {
                return;
            }
            nb.remove(nb.size() - 1);
            for (UndirectedGraphNode n2 : nb) {
                f3(n2);
            }
        }
        private void f4(UndirectedGraphNode n) {
            List<UndirectedGraphNode> nb = n.neighbors;
            if (nb.size() == 0 || nb.get(nb.size() - 1) != null) {
                return;
            }
            nb.remove(nb.size() - 1);
            for (UndirectedGraphNode n2 : nb) {
                f4(n2);
            }
        }
        public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
            if (node == null) {
                return null;
            }
            f1(node);
            List<UndirectedGraphNode> nb = node.neighbors;
            UndirectedGraphNode copy = nb.get(nb.size() - 1);
            f2(node);
            f3(node);
            f4(copy);
            return copy;
        }
    }

Log in to reply
 

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