题目

• 概述：给定一个嵌套的整型列表，设计一个迭代器，实现迭代器的核心功能：

  1. next()：输出下一个整数
  2. hasNext()： 判断是否有下一个整数

  使其能够遍历这个整型列表中的所有整数

• 输入：嵌套的整型列表

• 输入子项：整数或者整型列表

  注意：整型列表仍可能是嵌套的

• 输出：调用hasNext()判断是否有下一个整数，调用next()输出下一个整数

• 出处：https://leetcode-cn.com/problems/flatten-nested-list-iterator/

思路

• 根据整型列表拥有嵌套的特性，可以用栈保存嵌套信息

• 构造一个数据结构NestedIntegerWrap，该数据结构包含嵌套的整型列表，以及当前访问项的索引

• 以嵌套的整型列表和当前访问索引项0构造NestedIntegerWrap入栈

• hasNext()：栈为空返回false，反之true

• next()：重复观察栈顶元素，观察其包含的嵌套的整型列表的当前访问项，并让当前访问索引项+1，若+1后超过嵌套的整型列表的长度，则将其出栈：

  1. 若该元素为整数，返回该整数即可

  2. 若该元素为整型列表，则以整型列表和当前访问索引项0构造NestedIntegerWrap入栈

     若整型列表为空列表，则不入栈

• 由于存在嵌套的空列表的情况，所以采用预先计算下个值的方法来规避，当预先计算的下个值为空的情况则hasNext()返回false，否则返回true，调用next()方法时返回预先计算的下个值并预先计算下个值

代码

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * public interface NestedInteger {
 *
 *     // @return true if this NestedInteger holds a single integer, rather than a nested list.
 *     public boolean isInteger();
 *
 *     // @return the single integer that this NestedInteger holds, if it holds a single integer
 *     // Return null if this NestedInteger holds a nested list
 *     public Integer getInteger();
 *
 *     // @return the nested list that this NestedInteger holds, if it holds a nested list
 *     // Return null if this NestedInteger holds a single integer
 *     public List<NestedInteger> getList();
 * }
 */
public class NestedIterator implements Iterator<Integer> {
    private LinkedList<NestedIntegerWrap> stack = new LinkedList<>();
    //use pre-calculate nextVal avoid nested empty list case
    private Integer nextVal;
    
    public NestedIterator(List<NestedInteger> nestedList) {
        if (nestedList != null && nestedList.size() > 0) {
            stack.push(new NestedIntegerWrap(nestedList));
        }
        //first pre-calculate nextVal when new NestedIterator
        nextVal = getNext();
    }
    
    private Integer getNext() {
        NestedIntegerWrap top;
        NestedInteger val;
        List<NestedInteger> nestedList;
        while (!stack.isEmpty()) {
            top = stack.peek();
            if (!top.hasNext()) {
                stack.pop();
            }
            val = top.getNestedInteger();
            if (val.isInteger()) {
                return val.getInteger();
            } else {
                nestedList = val.getList();
                if (nestedList != null && nestedList.size() > 0) {
                    stack.push(new NestedIntegerWrap(nestedList));
                }
            }
        }
        return null;
    }

    //pre-calculate nextVal and return tempVal
    @Override
    public Integer next() {
        Integer tempVal = nextVal;
        nextVal = getNext();
        return tempVal;
    }

    //pre-calculate nextVal is null => hasNext is null
    @Override
    public boolean hasNext() {
        return nextVal != null;
    }
    
    class NestedIntegerWrap {
        List<NestedInteger> nestedList;
        int index;
        
        NestedIntegerWrap(List<NestedInteger> nestedList) {
            this.nestedList = nestedList;
        }
        
        boolean hasNext() {
            return index < nestedList.size() - 1;
        }
        
        NestedInteger getNestedInteger() {
            return nestedList.get(index++);
        }
    }
}