Easy to follow Java code, recursive solution, using "Staging area" to solve iterator problems


  • 0
    A
    public class NestedIterator implements Iterator<Integer> {
    // algorithm 2017/08/19: use a staging area. hasNext() prepare the staging area
    // since the data structure is recursively designed, the solution is also recursion based
    //  for each NestedInteger, if the content is a list, we recursively produce a NestedIterator based on that list
    public NestedIterator(List<NestedInteger> nestedList) {
        if (null == nestedList) {
            return;
        }
        m_iterator = nestedList.iterator();
    }
    
    @Override
    public Integer next() {
        return m_current;
    }
    
    @Override
    public boolean hasNext() {
        // find the first non-empty nestedInteger
        m_current = getNextInteger();
        return null != m_current;
    }
    
    // the main helper method to grab the next Integer
    private Integer getNextInteger() {
        if (null != m_nestedIter) {
            Integer nextInt = m_nestedIter.getNextInteger();
            if (null != nextInt) {
                return nextInt;
            } else {
                // nestIter is used up - need to grab the next 
            }
        }
        
        while (m_iterator.hasNext()) {
            NestedInteger ni = m_iterator.next();
            
            if (ni.isInteger()) {
                return ni.getInteger();
            } else {
                List<NestedInteger> listNIs = ni.getList();
                m_nestedIter                = new NestedIterator(listNIs);
                Integer        nextInt      = m_nestedIter.getNextInteger();
                if (null == nextInt) {
                    // go to the next NestedInteger -- back to while loop
                } else {
                    return nextInt;
                }
            }
        }
        
        return null;
    }
    
    private Integer m_current;      // a NestedInteger can be empty, and we need to skip the empty ones
    private Iterator<NestedInteger> m_iterator;
    private NestedIterator m_nestedIter;
    

    }

    /**

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

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.