Flatten Nested List Iterator解题报告

Description:

Given a nested list of integers, implement an iterator to flatten it.

Each element is either an integer, or a list -- whose elements may also be integers or other lists.

Example:

Example 1:
Given the list [[1,1],2,[1,1]],

By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1].

Example 2:
Given the list [1,[4,[6]]],

By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,4,6].

Link:

https://leetcode.com/problems/flatten-nested-list-iterator/description/

解题方法：

NestedIterator：
将vector里面的NestedInteger反过来亚入栈。
hasNext：
如果栈顶的NestedInteger是一个单独的数则返回true，否则从栈顶的这个List取出其中的NestedInteger，再反过来压栈，直到栈顶的元素是单独的数。
next：
从栈顶取出数即可。

Time Complexity：

NestedIterator：O(N)
next：O(1)

完整代码：

class NestedIterator 
{
private:
    stack<NestedInteger> container;
public:
    NestedIterator(vector<NestedInteger> &nestedList) 
    {
        for(int i = nestedList.size() - 1; i >= 0; i--)
        {
            container.push(nestedList[i]);
        }
    }
    int next() 
    {
        int result = container.top().getInteger();
        container.pop();
        return result;
    }
    bool hasNext() 
    {
        while(!container.empty())
        {
            NestedInteger curr = container.top();
            if(curr.isInteger())
                return true;
            container.pop();
            vector<NestedInteger> & currList = curr.getList();
            for(int i = currList.size() - 1; i >= 0; i--)
            {
                container.push(currList[i]);
            }
        }
        return false;
    }
};