[LeetCode] Gray Code

The gray code is a binary numeral system where two successive values differ in only one bit.

Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:

00 - 0
01 - 1
11 - 3
10 - 2
Note:
For a given n, a gray code sequence is not uniquely defined.

For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.

For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.

[Solution].java

import java.util.ArrayList;
import java.util.LinkedList;

public class Solution {
    public ArrayList<Integer> grayCode(int n) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        ArrayList<LinkedList<Integer>> codes = new ArrayList<LinkedList<Integer>>();
        if(n == 0){
            ArrayList<Integer> out = new ArrayList<Integer>();
            out.add(0);
            return out;
        }
        for(int i = 0; i <= 1; i++){
            LinkedList<Integer> init = new LinkedList<Integer>();
            init.add(i);
            codes.add(init);
        }
        for(int i = 2; i <= n; i++){
            ArrayList<LinkedList<Integer>> temp = new ArrayList<LinkedList<Integer>>();
            for(int j = codes.size() - 1; j >= 0; j--){
                LinkedList<Integer> newCode = new LinkedList<Integer>(codes.get(j));
                for(int k = i - newCode.size(); k >= 2; k--)
                    newCode.addFirst(0);
                newCode.addFirst(1);
                temp.add(newCode);
            }
            codes.addAll(temp);
        }
        ArrayList<Integer> out = new ArrayList<Integer>();
        for(LinkedList<Integer> code: codes) out.add(convert(code));
        return out;
    }
    
    public int convert(LinkedList<Integer> list){
        int sum = 0;
        for(Integer i: list) sum = sum * 2 + i;
        return sum;
    }
    
}