6ms recursive and non recusive solution


  • 0
    M
    public class NestedIterator implements Iterator<Integer> {
    
        List<Integer> list;
        int count;
        public NestedIterator(List<NestedInteger> nestedList) {
            this.list = new ArrayList<Integer>();
            this.count = 0;
            getListOfIntegers(nestedList,list);
        }
    
        @Override
        public Integer next() {
            return list.get(count++);
        }
    
        @Override
        public boolean hasNext() {
            return list.size()>count;
        }
        
        private void getListOfIntegers(List<NestedInteger> nestedList, List<Integer> list) {
            if(nestedList==null) return;
            
            for(NestedInteger i : nestedList) {
                if(i.isInteger()) list.add(i.getInteger());
                else getListOfIntegers(i.getList(),list);
            }
        }
    }
    

  • 0
    M

    Using stack

    public class NestedIterator implements Iterator<Integer> {
    
        Stack<Iterator<NestedInteger>> stack;
        Integer nextInteger;
        public NestedIterator(List<NestedInteger> nestedList) {
            stack = new Stack<Iterator<NestedInteger>>();
            stack.push(nestedList.iterator());
            nextInteger = null;
        }
    
        @Override
        public Integer next() {
            Integer next = null;
            if(hasNext()) {
                next = nextInteger;
                nextInteger=null;
            }
            return next;
        }
    
        @Override
        public boolean hasNext() {
            if(nextInteger==null) {
                while(!stack.isEmpty()) {
                    Iterator<NestedInteger> cIterator = stack.peek();
                    if(cIterator.hasNext()) {
                        NestedInteger c = cIterator.next();
                        if(c.isInteger()) {
                            nextInteger = c.getInteger();
                            return true;
                        } else {
                            stack.push(c.getList().iterator());
                        }
                    }
                    else stack.pop();
                }
                return false;
            } else return true;
        }
        
    }
    

  • 0
    M

    using a separate wrapper class: time 12 ms

    public class NestedIterator implements Iterator<Integer> {
    
        Stack<ListElement> stack;
        public NestedIterator(List<NestedInteger> nestedList) {
            stack = new Stack<ListElement>();
            stack.push(new ListElement(nestedList));
        }
    
        @Override
        public Integer next() {
            return hasNext()?stack.peek().next():null;
        }
    
        @Override
        public boolean hasNext() {
            while(!stack.isEmpty()) {
                ListElement cElement = stack.peek();
                if(cElement.hasNext()) {
                    NestedInteger c = cElement.get();
                    if(c.isInteger()) {
                        return true;
                    } else {
                        stack.push(new ListElement(c.getList()));
                        cElement.incrementCount();
                    }
                } else {
                    stack.pop();
                }
            }
            return false;
        }
        
    }
    
    class ListElement {
        private int count;
        private List<NestedInteger> list;
        public ListElement(List<NestedInteger> list) {
            this.list = list;
            this.count = 0;
        }
        public boolean hasNext() {
            return list.size()>count;
        }
        public Integer next() {
            Integer i =  get().getInteger();
            incrementCount();
            return i;
        }
        public NestedInteger get() {
            return list.get(this.count);
        }
        
        public void incrementCount() {
            this.count++;
        }
    }
    

Log in to reply
 

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