Simple Java Solution with stack


  • 0
    I
    public class NestedIterator implements Iterator<Integer> {
    
    private final List<NestedInteger> nestedList;
    private Stack<List<NestedInteger>> listStack = new Stack<>();
    private Stack<Integer> indexStack = new Stack<>();
    
    public NestedIterator(List<NestedInteger> nestedList) {
        this.nestedList = nestedList;
        indexStack.push(-1);
        listStack.push(this.nestedList);
        findNext();
    }
    
    @Override
    public Integer next() {
        Integer next = this.listStack.peek().get(this.indexStack.peek()).getInteger();
        findNext();
        return next;
    }
    
    @Override
    public boolean hasNext() {
        return !indexStack.isEmpty();
    }
    
    private void findNext() {
        boolean foundNext = false;
        while (!indexStack.isEmpty() && !foundNext) {
            int index = indexStack.pop();
            List<NestedInteger> list = listStack.pop();
            index++;
    
            while (index < list.size()) {
                if (list.get(index).isInteger()) {
                    indexStack.push(index);
                    listStack.push(list);
                    foundNext = true;
                    break;
                }
                // the current entry is a list. We only process a list that is not empty
                else {
                    if (list.get(index).getList().size() > 0){
                        listStack.push(list);
                        indexStack.push(index);
                        list = list.get(index).getList();
                        index = 0;
                    } else {
                        index++;
                    }
                }
            }
        }
    }
    
    }

Log in to reply
 

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