Java solution with inner iterator (no need for exhausting the original list)


  • 0
    B

    There are couple of solutions already, but some of them is building an inner List of NestedInteger.getList() items, which is unnecessary and space consuming (also, imagine a big list, at first step it will copy all the items to the inner stack in reverse order, just to return 1 item). We could use the original Lists, and just use their iterators. The solution goes like this:

    public class NestedIterator implements Iterator<Integer> {
    
        private Deque<Iterator<NestedInteger>> itStack;
        private Integer next;
    
        public NestedIterator(List<NestedInteger> nestedList) {
            itStack = new LinkedList<>();
            itStack.addFirst(nestedList.iterator());
        }
    
        @Override
        public Integer next() {
            if(!hasNext()) {
                throw new java.util.NoSuchElementException();
            }
            
            Integer result = next;
            next = null;
            return result;
        }
    
        @Override
        public boolean hasNext() {
            if(next != null) {
                return true;
            }
            
            while(!itStack.isEmpty()) {
                Iterator<NestedInteger> it = itStack.peekFirst();
                if(!it.hasNext()) {
                    itStack.removeFirst();
                } else {
                    NestedInteger ni = it.next();
                    if(ni.isInteger()) {
                        next = ni.getInteger();
                        return true;
                    } else {
                        itStack.addFirst(ni.getList().iterator());
                    }
                }
            }
            
            return false;
        }
    }
    

    We have a stack of Iterators. The tricky part is hasNext() which is responsible to get the first Integer result if exist and store it into next. The next() method is simple: return the already extracted value and reset our variable.

    This way next(), and hasNext() behaves the way one would expect: those can be invoked multiple times, and it will always return the right answer.


Log in to reply
 

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