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
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].
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].
LeetCode上的原题，请参见我之前的博客Flatten Nested List Iterator。但是不太明白的是，那篇博客中的解法三可以通过LeetCode的OJ，在LintCode上跑就有错误，不知道啥原因。
解法一：
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; };
本文转自博客园Grandyang的博客，原文链接：压平嵌套链表迭代器[LintCode] Flatten Nested List Iterator ，如需转载请自行联系原博主。
