LeetCode [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:

Input: [[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: [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].

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58

/** * // 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; * }; */ class NestedIterator { stack<vector<NestedInteger>::iterator> its, ends; public: NestedIterator(vector<NestedInteger> &nestedList) { its.push(nestedList.begin()); ends.push(nestedList.end()); } int next() { auto it = its.top(); int v = it->getInteger(); its.top()++; return v; } bool hasNext() { while(!its.empty()) { if(its.top() == ends.top()) { its.pop(); ends.pop(); } else { auto it = its.top(); if(it->isInteger()) return true; its.top()++;//current "it" is a list, and the list to stack and move to the next its.push(it->getList().begin()); ends.push(it->getList().end()); } } return false; } }; /** * Your NestedIterator object will be instantiated and called as such: * NestedIterator i(nestedList); * while (i.hasNext()) cout << i.next(); */