341. Flatten Nested List Iterator

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.

Example 1:
Given the list [[1,1],2,[1,1]],

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

Example 2:
Given the list [1,[4,[6]]],

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

Solution:

Iterative: Stack

Use a stack to maintain all the flattened integer. If the current nestedInteger is a list, we push its elements(last->first) to the stack. Make sure all the elements in the stack are integers.

 public class NestedIterator implements Iterator<Integer> {  
   Stack<NestedInteger> st;  
   public NestedIterator(List<NestedInteger> nestedList) {  
     st=new Stack<NestedInteger>();  
     for(int i=nestedList.size()-1;i>=0;i--){  
       st.push(nestedList.get(i));  
     }  
   }  
   @Override  
   public Integer next() {  
     return st.pop().getInteger();  
   }  
   @Override  
   public boolean hasNext() {      
     while(!st.empty() && !st.peek().isInteger()){  
       List<NestedInteger> li=st.pop().getList();  
        for(int i=li.size()-1;i>=0;i--){  
       st.push(li.get(i));  
     }  
     }  
      if(st.empty()) return false;  
     return true;  
   }  
 }  

Another solution is kind of recursive solution. We recursively use the NestedIterator to iterate nested list. Backtrack to current list when the next iterator doesn't have next element.

 public class NestedIterator implements Iterator<Integer> {  
   NestedIterator nextIt;  
   Iterator<NestedInteger> itr;  
   Integer nextInt;  
   public NestedIterator(List<NestedInteger> nestedList) {  
     itr=nestedList.iterator();  
     nextIt=null;  
     nextInt=null;  
   }  
   @Override  
   public Integer next() {  
     if(nextIt!=null) return nextIt.next();  
     return nextInt;  
   }  
   @Override  
   public boolean hasNext() {  
     if(nextIt!=null && nextIt.hasNext()) return true;  
     while(itr.hasNext()){  
       NestedInteger nextNestedInteger=itr.next();  
       nextIt=null;  
       if(nextNestedInteger.isInteger()){  
         nextInt=nextNestedInteger.getInteger();  
         return true;  
       }  
       else{  
         nextIt=new NestedIterator(nextNestedInteger.getList());  
         if(nextIt.hasNext()) return true;  
       }  
     }  
     return false;  
   }  
 }