My 5ms iterator+stack solution with explaination


  • 0
    X

    I use nested iterators to iterate the whole list. Each time the iterator returns an Integer, I print it out. Each time the iterator returns an list-like NestedInteger, I store the iterator into a stack and get a new iterator for the returned one.

    public class NestedIterator implements Iterator<Integer> {
        private Stack<Iterator<NestedInteger>> stack;
        private Iterator<NestedInteger> curIterator;
        private Integer i;
        
        public NestedIterator(List<NestedInteger> nestedList) {
            stack = new Stack<>();
            curIterator = nestedList.iterator();
        }
    
        @Override
        public Integer next() {
            return i;
        }
    
        @Override
        public boolean hasNext() {
            if (curIterator.hasNext()) {
                NestedInteger cur = curIterator.next();
                if (cur.isInteger()) {
                    i = cur.getInteger();
                    return true;
                }
                
                // not Integer
                stack.push(curIterator);
                curIterator = cur.getList().iterator();
                return this.hasNext();
                
            } else {
                // curIterator has no next
                while (!stack.isEmpty() && !curIterator.hasNext()) {
                    curIterator = stack.pop();
                }
                
                if (curIterator.hasNext()) return this.hasNext();
                return false;
            }
        }
    }
    

Log in to reply
 

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