扁平化嵌套列表迭代器

[louzhedong]

习题

给你一个嵌套的整型列表。请你设计一个迭代器，使其能够遍历这个整型列表中的所有整数。

列表中的每一项或者为一个整数，或者是另一个列表。其中列表的元素也可能是整数或是其他列表。

示例 1:

输入: [[1,1],2,[1,1]]
输出: [1,1,2,1,1]
解释: 通过重复调用 next 直到 hasNext 返回 false，next 返回的元素的顺序应该是: [1,1,2,1,1]。
示例 2:

输入: [1,[4,[6]]]
输出: [1,4,6]
解释: 通过重复调用 next 直到 hasNext 返回 false，next 返回的元素的顺序应该是: [1,4,6]。

思路

列表本身就是一个栈，取下一个，即从列表头部取出一个数据，如果该值还是一个列表，反向遍历该列表，从头部推入栈中，再从中取出第一个元素，往复循环，当当前元素是数字时，进行输出

刚开始考虑的是在next方法中执行上述的操作，但在判断当前列表hasNext时就会判断第一个元素的类型，因为需要处理[[]]的情况，所以也可以将上述操作放在hasNext方法里，next方法每次只需要输出第一个元素即可

注意点：要利用上面备注中给出的方法，因为元素一个NestedInteger的特殊类型

解答

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * function NestedInteger() {
 *
 *     Return true if this NestedInteger holds a single integer, rather than a nested list.
 *     @return {boolean}
 *     this.isInteger = function() {
 *         ...
 *     };
 *
 *     Return the single integer that this NestedInteger holds, if it holds a single integer
 *     Return null if this NestedInteger holds a nested list
 *     @return {integer}
 *     this.getInteger = function() {
 *         ...
 *     };
 *
 *     Return the nested list that this NestedInteger holds, if it holds a nested list
 *     Return null if this NestedInteger holds a single integer
 *     @return {NestedInteger[]}
 *     this.getList = function() {
 *         ...
 *     };
 * };
 */
/**
 * @constructor
 * @param {NestedInteger[]} nestedList
 */
var NestedIterator = function (nestedList) {
    this.nestedList = nestedList;
};


/**
 * @this NestedIterator
 * @returns {boolean}
 */
NestedIterator.prototype.hasNext = function () {
    while (this.nestedList.length != 0) {
        if (this.nestedList[0].isInteger()) {
            return true;
        } else {
            let top = this.nestedList.shift();
            let list = top.getList();
            for (let i = list.length - 1; i >= 0; i--) {
                this.nestedList.unshift(list[i]);
            }
        }
    }
};

/**
 * @this NestedIterator
 * @returns {integer}
 */
NestedIterator.prototype.next = function () {
    return this.nestedList.shift().getInteger();
};


/**
 * Your NestedIterator will be called like this:
 * var i = new NestedIterator(nestedList), a = [];
 * while (i.hasNext()) a.push(i.next());
*/