solution.md

# 扁平化嵌套列表迭代器

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

<p>实现扁平迭代器类 <code>NestedIterator</code> ：</p>

<ul>
	<li><code>NestedIterator(List&lt;NestedInteger&gt; nestedList)</code> 用嵌套列表 <code>nestedList</code> 初始化迭代器。</li>
	<li><code>int next()</code> 返回嵌套列表的下一个整数。</li>
	<li><code>boolean hasNext()</code> 如果仍然存在待迭代的整数，返回 <code>true</code> ；否则，返回 <code>false</code> 。</li>
</ul>

<p>你的代码将会用下述伪代码检测：</p>

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

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

<p>&nbsp;</p>

<p><strong>示例 1：</strong></p>

<pre>
<strong>输入：</strong>nestedList = [[1,1],2,[1,1]]
<strong>输出：</strong>[1,1,2,1,1]
<strong>解释：</strong>通过重复调用&nbsp;<em>next </em>直到&nbsp;<em>hasNex</em>t 返回 false，<em>next&nbsp;</em>返回的元素的顺序应该是: <code>[1,1,2,1,1]</code>。</pre>

<p><strong>示例 2：</strong></p>

<pre>
<strong>输入：</strong>nestedList = [1,[4,[6]]]
<strong>输出：</strong>[1,4,6]
<strong>解释：</strong>通过重复调用&nbsp;<em>next&nbsp;</em>直到&nbsp;<em>hasNex</em>t 返回 false，<em>next&nbsp;</em>返回的元素的顺序应该是: <code>[1,4,6]</code>。
</pre>

<p>&nbsp;</p>

<p><strong>提示：</strong></p>

<ul>
	<li><code>1 &lt;= nestedList.length &lt;= 500</code></li>
	<li>嵌套列表中的整数值在范围 <code>[-10<sup>6</sup>, 10<sup>6</sup>]</code> 内</li>
</ul>

<p>以下<span style="color:red">错误</span>的选项是？</p>

## aop

### before

```cpp
#include <bits/stdc++.h>
using namespace std;

// This is the interface that allows for creating nested lists.
// You should not implement it, or speculate about its implementation
class NestedInteger
{
public:
    // Return true if this NestedInteger holds a single integer, rather than a nested list.
    bool isInteger() const;

    // Return the single integer that this NestedInteger holds, if it holds a single integer
    // The result is undefined if this NestedInteger holds a nested list
    int getInteger() const;

    // Return the nested list that this NestedInteger holds, if it holds a nested list
    // The result is undefined if this NestedInteger holds a single integer
    const vector<NestedInteger> &getList() const;
};
```
### after

```cpp

```

## 答案

```cpp
class NestedIterator
{
public:
    vector<int> data;
    vector<int>::iterator it;

    NestedIterator(vector<NestedInteger> &nestedList)
    {
        parse(nestedList);
        it = data.begin();
    }

    void parse(vector<NestedInteger> &nestedList)
    {
        for (auto nes : nestedList)
        {

            data.push_back(nes.getInteger());
            parse(nes.getList());
        }
    }

    int next()
    {
        return *it++;
    }

    bool hasNext()
    {
        return it != data.end();
    }
};
```
## 选项

### A
```cpp
class NestedIterator
{
public:
    stack<NestedInteger *> st;
    NestedIterator(vector<NestedInteger> &nestedList)
    {
        for (int i = nestedList.size() - 1; i >= 0; --i)
            st.push(&nestedList[i]);
    }

    int next()
    {
        int res = st.top()->getInteger();
        st.pop();
        return res;
    }

    bool hasNext()
    {
        if (st.empty())
            return false;
        NestedInteger *tmp = st.top();
        while (!tmp->isInteger())
        {
            st.pop();
            vector<NestedInteger> &list = tmp->getList();
            for (int i = list.size() - 1; i >= 0; --i)
                st.push(&list[i]);
            if (st.empty())
                return false;
            tmp = st.top();
        }
        return true;
    }
};
```

### B
```cpp
class NestedIterator
{
public:
    int cnt = 0;
    vector<int> ans;

    void dfs(vector<NestedInteger> &nestedList)
    {
        for (auto l : nestedList)
        {
            if (l.isInteger())
                ans.push_back(l.getInteger());
            else
                dfs(l.getList());
        }
    }

    NestedIterator(vector<NestedInteger> &nestedList)
    {
        dfs(nestedList);
    }

    int next()
    {
        return ans[cnt++];
    }

    bool hasNext()
    {
        return cnt < ans.size();
    }
};
```

### C
```cpp
class NestedIterator
{
    stack<vector<NestedInteger>::iterator> begins, ends;

public:
    NestedIterator(vector<NestedInteger> &nestedList)
    {
        begins.push(nestedList.begin());
        ends.push(nestedList.end());
    }

    int next()
    {
        hasNext();
        return (begins.top()++)->getInteger();
    }

    bool hasNext()
    {
        vector<NestedInteger>::iterator tp;
        while (!begins.empty())
        {
            if (begins.top() == ends.top())
            {
                begins.pop();
                ends.pop();
            }
            else
            {
                tp = begins.top();
                if (tp->isInteger())
                    return true;

                begins.top()++;

                begins.push(tp->getList().begin());
                ends.push(tp->getList().end());
                ;
            }
        }
        return false;
    }
};
```