Flatten Nested List Iterator

Problem:
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].

Analysis:
3/16/2018 update:
Remember to call hasNext() in next() to make sure no error.
public class NestedIterator implements Iterator<Integer> {
    Stack<NestedInteger> stack = new Stack<>();
    public NestedIterator(List<NestedInteger> nestedList) {
        pushToStack(nestedList);
    }

    @Override
    public Integer next() {
        return hasNext() ? stack.pop().getInteger() : null;
    }

    @Override
    public boolean hasNext() {
        while (!stack.isEmpty()) {
            NestedInteger cur = stack.peek();
            if (cur.isInteger()) {
                return true;
            }
            stack.pop();
            pushToStack(cur.getList());
        }
        return false;
    }

    private void pushToStack(List<NestedInteger> list) {
        for (int i = list.size() - 1; i >= 0; i--) {
            stack.push(list.get(i));
        }           
    }
}


--------------------------------------------------------------------------------------------------------------------------
Use stack to flat the nested list. Push items to stack in reverse order. When determine hasNext, if the stack top is not Integer, then flat it.
Solution:


 /**  
  * // 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;  
   public NestedIterator(List<NestedInteger> nestedList) {  
     // Initialize your data structure here.  
     stack = new Stack<>();  
     updateStack(nestedList);  
   }  
   private void updateStack(List<NestedInteger> nestedList) {  
     Stack<NestedInteger> temp = new Stack<>();  
     for (NestedInteger n: nestedList) {  
       temp.push(n);  
     }  
     while (!temp.isEmpty()) {  
       stack.push(temp.pop());  
     }  
   }  
   // @return {int} the next element in the iteration  
   @Override  
   public Integer next() {  
     // Write your code here  
     if(!hasNext()) {  
       return null;  
     }  
     return stack.pop().getInteger();  
   }  
   // @return {boolean} true if the iteration has more element or false  
   @Override  
   public boolean hasNext() {  
     // Write your code here  
     // get next  
     while (!stack.isEmpty() && !stack.peek().isInteger()) {  
       updateStack(stack.pop().getList());  
     }  
     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());  
  */  

评论

此博客中的热门博文

776. Split BST

663. Equal Tree Partition

532. K-diff Pairs in an Array