# 341. Flatten Nested List Iterator

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 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]`.

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

int next() {
NestedInteger t = s.top(); s.pop();
return t.getInteger();
}

bool hasNext() {
while (!s.empty()) {
NestedInteger t = s.top();
if (t.isInteger()) return true;
s.pop();
for (int i = t.getList().size() - 1; i >= 0; --i) {
s.push(t.getList()[i]);
}
}
return false;
}

private:
stack<NestedInteger> s;
};
``````

``````class NestedIterator {
public:
NestedIterator(vector<NestedInteger> &nestedList) {
for (auto a : nestedList) {
d.push_back(a);
}
}

int next() {
NestedInteger t = d.front(); d.pop_front();
return t.getInteger();
}

bool hasNext() {
while (!d.empty()) {
NestedInteger t = d.front();
if (t.isInteger()) return true;
d.pop_front();
for (int i = 0; i < t.getList().size(); ++i) {
d.insert(d.begin() + i, t.getList()[i]);
}
}
return false;
}

private:
deque<NestedInteger> d;
};
``````

``````class NestedIterator {
public:
NestedIterator(vector<NestedInteger> &nestedList) {
make_queue(nestedList);
}

int next() {
int t = q.front(); q.pop();
return t;
}

bool hasNext() {
return !q.empty();
}

private:
queue<int> q;
void make_queue(vector<NestedInteger> &nestedList) {
for (auto a : nestedList) {
if (a.isInteger()) q.push(a.getInteger());
else make_queue(a.getList());
}
}
};
``````

Nested List Weight Sum

Flatten 2D Vector

Zigzag Iterator

https://leetcode.com/discuss/95841/simple-solution-with-queue

https://leetcode.com/discuss/95892/concise-c-without-storing-all-values-at-initialization

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation