Problem

Implement an iterator to flatten a 2d vector.

Example
Given 2d vector =

[
  [1,2],
  [3],
  [4,5,6]
]
By calling next repeatedly until hasNext returns false, 
    the order of elements returned by next should be: [1,2,3,4,5,6].

思路一 (Two stack)

1. because we don't know how many lists are nested, we need a stack to store the flatten list. 
2. the front elements in the list should be the last one to be pushed into the stack, so we need another stack to reverse the order
例子:
        [[1,1],2,[1,1]]     ->      [1,1,2,1,1]
        [1,[4,[6]]]         ->      [1,4,6]
        [[[[1,2],3],4],5]   ->      [1,2,3,4,5]

Notice

• hasNext()
  • 之前直接return true 这部我出错了,
  • test case: [[],[]]
  • 因为stack一开始不为空, 调用pushListToStack()后变成空的了.

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * 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();
 * }
 */
import java.util.Iterator;

public class NestedIterator implements Iterator<Integer> {

    private Stack<NestedInteger> stack;

    private void pushListToStack(List<NestedInteger> nestedList) {
        if (nestedList == null || nestedList.isEmpty()) {
            return;
        }
        Stack<NestedInteger> temp = new Stack<>();
        for (NestedInteger ni: nestedList) {
            temp.push(ni);
        }
        while (!temp.isEmpty()) {
            stack.push(temp.pop());
        }
    }

    public NestedIterator(List<NestedInteger> nestedList) {
        stack = new Stack<>();
        pushListToStack(nestedList);
    }

    // @return {int} the next element in the iteration
    @Override
    public Integer next() {
        if (!hasNext()) {
            return null;
        }
        return stack.pop().getInteger();
    }

    // @return {boolean} true if the iteration has more element or false
    @Override
    public boolean hasNext() {
        if (stack.isEmpty()) {
            return false;
        }
        while (!stack.isEmpty() && !stack.peek().isInteger()) {
            pushListToStack(stack.pop().getList());
        }

        // 之前直接return true 这部我出错了, 
        // test case: [[],[]]
        // 因为stack一开始不为空, 调用pushListToStack()后变成空的了.
        return !stack.isEmpty();
    }

    @Override
    public void remove() {}
}

/**
 * Your NestedIterator object will be instantiated and called as such:
 * NestedIterator i = new NestedIterator(nestedList);
 * while (i.hasNext()) v.add(i.next());
 */

思路二(一个linkedList)

• 两个stack的工作能够被一个linkedList 代替

public class NestedIterator implements Iterator<Integer> {

    private LinkedList<NestedInteger> list;

    public NestedIterator(List<NestedInteger> nestedList) {
        list = new LinkedList<>(nestedList);
    }

    // @return {int} the next element in the iteration
    @Override
    public Integer next() {
        if (!hasNext()) {
            return null;
        }
        return list.remove().getInteger();
    }

    // @return {boolean} true if the iteration has more element or false
    @Override
    public boolean hasNext() {
        while (!list.isEmpty() && !list.peek().isInteger()) {
            List<NestedInteger> nis = list.removeFirst().getList();
            for (int i = nis.size() - 1; i >= 0; i--) {
                list.addFirst(nis.get(i));
            }
        }
        return !list.isEmpty();
    }

    @Override
    public void remove() {}
}