# 341 Flatten Nested List Iterator

• Idea:

  1. use a queue to store all elements.
  2. next():
     return queue.poll();
  3. hasNext():
     if the front of the queue is integer, return true.
     otherwise, poll an element from queue, and push into queue.

• Note:

  1. 一開始我想在next()裡面判斷queue的最前面的element是不是integer，再return，然後hasNext()只回傳!queue.isEmpty()，後來發現無法處理這個case:

  [[[[]]], []]
  

  -- list裡面都是空list的情況，才改成讓next()只回傳queue的最前方element，由hasNext()來處理queue，使 queue的第一個一定是integer。後來想想這樣的確比較合理，因為iterator通常要通過hasNext()，才呼叫next()，所以應該是hasNext()要有達到保證next()可以取到正確值的功能。這題和Google當初我被問的題目有點類似～

  1. 這題值得注意的第二點是Iterator的架構: implements, @Override

• Code

/**
 * // 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();
 * }
 */


public class NestedIterator implements Iterator<Integer> {

    Deque<NestedInteger> deque = new ArrayDeque<>();

    public NestedIterator(List<NestedInteger> nestedList) {
        for(int i=0; i< nestedList.size(); i++){//add all elements in nested List to deque
            deque.offer(nestedList.get(i));
        }
    }

    @Override
    public Integer next() {
        return deque.poll().getInteger();// the first element in deque is guaranteed to be integer
    }

    @Override
    public boolean hasNext() {
        while(!deque.isEmpty()){
            if(deque.peek().isInteger())
                return true;
            NestedInteger n = deque.poll();
            List<NestedInteger> list = n.getList();
            for(int i=list.size()-1; i>=0; i--){ //把NestedList拆開，放回deque，為了保持順序而從前面塞進去
                deque.offerFirst(list.get(i));
            }
        }
        return false;
    }
}

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