341. Flatten Nested List Iterator

1. Description

You are given a nested list of integers nestedList. Each element is either an integer or a list whose elements may also be integers or other lists. Implement an iterator to flatten it.
Implement the NestedIterator class:

• NestedIterator(List nestedList) Initializes the iterator with the nested list nestedList.
• int next() Returns the next integer in the nested list.
• boolean hasNext() Returns true if there are still some integers in the nested list and false otherwise.

Your code will be tested with the following pseudocode:

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

If res matches the expected flattened list, then your code will be judged as correct.

2. Example

Example 1:
Input: nestedList = [[1,1],2,[1,1]]
Output: [1,1,2,1,1]
Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1].

Example 2:
Input: nestedList = [1,[4,[6]]]
Output: [1,4,6]
Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,4,6].

3. Constraints

• 1 <= nestedList.length <= 500
• The values of the integers in the nested list is in the range [$-10^6$, $10^6$].

4. Solutions

Stack

n is the number of integers in nestedList
Space complexity: O(n)

class NestedIterator {
public:
    NestedIterator(const vector<NestedInteger> &nestedList) {
        data_.emplace(nestedList.begin(), nestedList.end());
    }

    int next() {
    // Time complexity: O(1)
        auto &iter = data_.top();
        int value = iter.first->getInteger();
        ++iter.first;

        return value;
    }

    bool hasNext() {
    // Time complexity: O(1)
        while (!data_.empty()) {
            auto &iter = data_.top();
            if (iter.first == iter.second) {
                data_.pop();
                continue;
            }

            if (iter.first->isInteger()) {
                return true;
            }

            auto &new_iter = iter.first->getList();
            data_.emplace(new_iter.begin(), new_iter.end());
            ++iter.first;
        }

        return false;
    }

private:
    // curent iter and end iter
    stack<pair<vector<NestedInteger>::iterator, vector<NestedInteger>::iterator>> data_;
};