341. Flatten Nested List Iterator

Since there could be a lot of nested list, the intuition is to use stack, i.e. stack up the nested list and deal with the most inner list first.
The idea is keep stacking up all the elements in the list until the top element in the stack is not a nested list any more.
So in the constructor, we stack up all the elements in the list. Since we call hasNext() before next(), we'll process the stack mainly in the hasNext() interface. We get the top element in the stack. There'll be two cases:

Case 1: top element is an integer.
This is the easiest case where we return true. Since the next() interface needs this element so we'll leave the pop action in next().

Case 2: top element is a list.
Now we need to get the list and pop out this element in the stack. And then push all the elements in the list into stack. And then go back and check the top element again.

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, rather than a nested list.  
7:   *   bool isInteger() const;  
8:   *  
9:   *   // Return the single integer that this NestedInteger holds, if it holds a single integer  
10:   *   // The result is undefined if this NestedInteger holds a nested list  
11:   *   int getInteger() const;  
12:   *  
13:   *   // Return the nested list that this NestedInteger holds, if it holds a nested list  
14:   *   // The result is undefined if this NestedInteger holds a single integer  
15:   *   const vector<NestedInteger> &getList() const;  
16:   * };  
17:   */  
18:  class NestedIterator {  
19:  private:  
20:    stack<NestedInteger> stk;  
21:  public:  
22:    NestedIterator(vector<NestedInteger> &nestedList) {  
23:      for (int i = nestedList.size()-1; i >= 0; i--) {  
24:        stk.push(nestedList[i]);  
25:      }  
26:    }  
27:    int next() {  
28:      int val = stk.top().getInteger();  
29:      stk.pop();  
30:      return val;  
31:    }  
32:    bool hasNext() {  
33:      while (!stk.empty()) {  
34:        NestedInteger cur = stk.top();  
35:        if (cur.isInteger()) return true;  
36:        stk.pop();  
37:        vector<NestedInteger> &list = cur.getList();  
38:        for (int i = list.size()-1; i >= 0; i--) {  
39:          stk.push(list[i]);  
40:        }  
41:      }  
42:      return false;  
43:    }  
44:  };  
45:  /**  
46:   * Your NestedIterator object will be instantiated and called as such:  
47:   * NestedIterator i(nestedList);  
48:   * while (i.hasNext()) cout << i.next();  
49:   */  

When I revisited this problem, I tried to flat the list in next() function as following. However, it will get a runtime error if the input is "[[]]". The reason is the hasNext() simply checks if the stack is empty and thus will return true here. But in fact, it should be false. So we must flat the list in hasNext() function. Also I made a syntax error in line 32.

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, rather than a nested list.  
7:   *   bool isInteger() const;  
8:   *  
9:   *   // Return the single integer that this NestedInteger holds, if it holds a single integer  
10:   *   // The result is undefined if this NestedInteger holds a nested list  
11:   *   int getInteger() const;  
12:   *  
13:   *   // Return the nested list that this NestedInteger holds, if it holds a nested list  
14:   *   // The result is undefined if this NestedInteger holds a single integer  
15:   *   const vector<NestedInteger> &getList() const;  
16:   * };  
17:   */  
18:  class NestedIterator {  
19:  private:  
20:    stack<NestedInteger> stk;  
21:  public:  
22:    NestedIterator(vector<NestedInteger> &nestedList) {  
23:      int n = nestedList.size();  
24:      for (int i = n-1; i >= 0; i--) {  
25:        stk.push(nestedList[i]);  
26:      }  
27:    }  
28:    int next() {  
29:      while (!stk.top().isInteger()) {  
30:        NestedInteger t = stk.top();  
31:        stk.pop();  
32:        vector<NestedInteger> &list = t.getList();  
33:        int n = list.size();  
34:        for (int i = n-1; i >= 0; i--) {  
35:          stk.push(list[i]);  
36:        }  
37:      }  
38:      int ret = stk.top().getInteger();  
39:      stk.pop();  
40:      return ret;  
41:    }  
42:    bool hasNext() {  
43:      return !stk.empty();  
44:    }  
45:  };  
46:  /**  
47:   * Your NestedIterator object will be instantiated and called as such:  
48:   * NestedIterator i(nestedList);  
49:   * while (i.hasNext()) cout << i.next();  
50:   */