leetcode-341 扁平化嵌套列表迭代器

题目描述：给你一个嵌套的整数列表 nestedList 。每个元素要么是一个整数，要么是一个列表；该列表的元素也可能是整数或者是其他列表。请你实现一个迭代器将其扁平化，使之能够遍历这个列表中的所有整数。

实现扁平迭代器类 NestedIterator ：

1. NestedIterator(List nestedList) 用嵌套列表 nestedList 初始化迭代器。

• int next() 返回嵌套列表的下一个整数。

• boolean hasNext() 如果仍然存在待迭代的整数，返回 true ；否则，返回 false 。
  你的代码将会用下述伪代码检测：

initialize iterator with nestedList
res = []
while iterator.hasNext()
    append iterator.next() to the end of res
return res

如果 res 与预期的扁平化列表匹配，那么你的代码将会被判为正确。

代码实现

NestedInteger

public class NestedInteger {
    private List<NestedInteger> list;

    private Integer node;

    public NestedInteger(Integer node) {
        this.node = node;
        this.list = null;
    }

    public NestedInteger(List<NestedInteger> list) {
        this.list = list;
        this.node = null;
    }

    public Boolean isInteger() {
        return this.node != null;
    }

    public Integer getInteger() {
        return this.node;
    }

    public List<NestedInteger> getList() {
        return this.list;
    }
}

递归实现

class NestedIterator implements Iterator<Integer> {
    private Iterator<Integer> it;

    public NestedIterator(List<NestedInteger> nestedList) {
        //1. 扁平化展开嵌套列表
        List<Integer> list = new ArrayList<>();
        for (NestedInteger nit : nestedList) {
            traverse(nit, list);
        }

        //2. 处理展开后的列表
        this.it = list.iterator();
    }

    @Override
    public Integer next() {
        return this.it.next();
    }

    @Override
    public boolean hasNext() {
        return this.it.hasNext();
    }

    /**
     * 递归展开列表
     *
     * @param nit  NestedInteger
     * @param list List<Integer>
     */
    private void traverse(NestedInteger nit, List<Integer> list) {
        if (nit.isInteger()) {
            list.add(nit.getInteger());
            return;
        }
        for (NestedInteger childNit : nit.getList()) {
            traverse(childNit, list);
        }
    }
}

惰性实现

class NestedIterator implements Iterator<Integer> {
    private LinkedList<NestedInteger> it;

    public NestedIterator(List<NestedInteger> nestedList) {
        this.it = new LinkedList<>(nestedList);
    }
    
    @Override
    public Integer next() {
        return this.it.remove(0).getInteger();
    }

    /**
     * 判断下一个原始是否是Integer
     * 如果是Integer则直接返回
     * 如果不是则使用头插法展开
     *
     * @return
     */
    @Override
    public boolean hasNext() {
        while (!this.it.isEmpty() && !this.it.get(0).isInteger()) {
            List<NestedInteger> nit = this.it.remove(0).getList();
            for (int i = nit.size() - 1; i >= 0; i--) {
                this.it.addFirst(nit.get(i));
            }
        }
        return !this.it.isEmpty();
    }
}