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

• 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;
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;
f2(n2);
}
}
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;
}
}

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