public class Solution {
public List<Integer> grayCode(int n) {
List<Integer> prev = new LinkedList<>();
prev.add(0);
if(n == 0){
return prev;
}
List<Integer> current = new LinkedList<>();
for(int i = 1; i <= n; i++){
for(int j=0; j<prev.size(); j++){
int temp = prev.get(j)<<1;
// alternate 0 and 1 for each previous sequence
if(j%2 == 0){
current.add(temp);
current.add(temp+1);
}else{
current.add(temp+1);
current.add(temp);
}
}
prev = current;
current = new LinkedList<>();
}
return prev;
}
}
Simple Java Solution based on observation


I believe the observation is that the nth sequence and the n+1th sequence always have one digit in difference, therefore we can left shift the nth sequence, add 0 then 1; left shift the n+1th sequence, add 1 then 0 to generate new sequences that still only differ in one digit. Try it out with some examples. (0,1), (00, 01, 11, 10),(000,001,011,010,110,111,101,100). Does it make sense?

Oh I missed the shift, so it's like taking the existing reversed and adding a 1 at the beginning just adding doing it from the back and having some magic property of this "recursion" help to keep the order.
Thank, you I see the pattern, but not the why, yet.