public List<Integer> grayCode(int n) {
List<Integer> ans = new LinkedList<Integer>();
if (n == 0) {
ans.add(0);
return ans;
}
List<Integer> previous = grayCode(n  1);
int factor = 1 << (n  1);
for (int num : previous) {
ans.add(ans.size() / 2, num);
ans.add(1 + ans.size() / 2, num + factor);
}
return ans;
}
Java Concise 10Line Simple Solution


Complexity explodes: adding an item to a linked list at position
i
is a linear operation, same with array list. Linked list needs to findi
th link node inside which takesi
steps, array list would find it immediately, but inserting needs to moveni
elements.This means that the for loop is
O(n^2)
, right? I think if you iterate twice, copying the previous result and then copying the result in reverse and addingfactor
would reduce it to2n
. You can even use the same list if you save the size before iterations and only copy that many elements.