Given a nested list of integers, implement an iterator to flatten it.

Each element is either an integer, or a list – whose elements may also be integers or other lists.


Input              Result
[1, 2, 3]          [1, 2, 3]
[[1,1],2,[1,1]]    [1,1,2,1,1]
[1,[4,[6]]]        [1,4,6]

We use the following ListIndex class for backtracking.

class ListIndex {
    public List<NestedInteger> list;
    public int index;
    public ListIndex(List<NestedInteger> list, int index) {
        this.list = list;
        this.index = index;

The following algorithm uses the ListIndex class above to perform the search using a stack.

import java.util.Iterator;

public class NestedIterator implements Iterator<Integer> {
    Stack<ListIndex> stack;   //Stack for backtracking
    List<NestedInteger> curr; //The current list
    int index;                //The current index
    public NestedIterator(List<NestedInteger> nestedList) {
        stack = new Stack<ListIndex>();
        curr = nestedList;
        index = -1;

     * Find the next non-list integer.
    private void findNext() {
        while (true) {
            //If we reach the end of this list, then, we either
            //pop the stack to backtrack or we are finished.
            if (index == curr.size()) {
                //Reached the end of everything
                if (stack.isEmpty())
                //Pop the stack to backtrack
                ListIndex listIndex = stack.pop();
                curr = listIndex.list;
                index = listIndex.index;
            else { //Index is not at the end of current list
                NestedInteger i = curr.get(index);
                //Found next item
                if (i.isInteger())
                //Push current list and search child list
                stack.push(new ListIndex(curr, index));
                curr = i.getList();
                index = -1;
    // @return {int} the next element in the iteration
    public Integer next() {
        Integer res = curr.get(index).getInteger();
        return res;

    // @return {boolean} true if the iteration has more element or false
    public boolean hasNext() {
        return index < curr.size();

    public void remove() {}
    //Your NestedIterator object will be instantiated and called as such:
    NestedIterator i = new NestedIterator(nestedList);
    while (i.hasNext()) v.add(;
public interface NestedInteger {

    // @return true if this NestedInteger holds a single integer,
    // rather than a nested list.
    public boolean isInteger();

    // @return the single integer that this NestedInteger holds,
    // if it holds a single integer
    // Return null if this NestedInteger holds a nested list
    public Integer getInteger();

    // @return the nested list that this NestedInteger holds,
    // if it holds a nested list
    // Return null if this NestedInteger holds a single integer
    public List<NestedInteger> getList();