首页 > 代码库 > Flatten Nested List Iterator

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

 

Runtime: 626ms

 1 /** 2  * // This is the interface that allows for creating nested lists. 3  * // You should not implement it, or speculate about its implementation 4  * class NestedInteger { 5  *   public: 6  *     // Return true if this NestedInteger holds a single integer, 7  *     // rather than a nested list. 8  *     bool isInteger() const; 9  *10  *     // Return the single integer that this NestedInteger holds,11  *     // if it holds a single integer12  *     // The result is undefined if this NestedInteger holds a nested list13  *     int getInteger() const;14  *15  *     // Return the nested list that this NestedInteger holds,16  *     // if it holds a nested list17  *     // The result is undefined if this NestedInteger holds a single integer18  *     const vector<NestedInteger> &getList() const;19  * };20  */21 class NestedIterator {22 public:23     NestedIterator(vector<NestedInteger> &nestedList) {24         // Initialize your data structure here.25         flatten(nestedList, result);26         index = 0;27     }28 29     // @return {int} the next element in the iteration30     int next() {31         // Write your code here32         return result[index++];33     }34 35     // @return {boolean} true if the iteration has more element or false36     bool hasNext() {37         // Write your code here38         return index < result.size();39     }40     41 private:42     vector<int> result;43     int index;44     45     void flatten(vector<NestedInteger> nestedList, vector<int>& result) {46         for (int i = 0; i < nestedList.size(); i++) {47             if (nestedList[i].isInteger())48                 result.push_back(nestedList[i].getInteger());49             else 50                 flatten(nestedList[i].getList(), result);51         }52     }53 };54 55 /**56  * Your NestedIterator object will be instantiated and called as such:57  * NestedIterator i(nestedList);58  * while (i.hasNext()) v.push_back(i.next());59  */

 

Flatten Nested List Iterator