Concise iterative solution in C++


  • 0
    L

    basically DFS, use a stack to keep track of the begin and end of each list.

    #include <string>
    #include<vector>
    using namespace std;
    
    
    typedef vector<NestedInteger>  ints;
    class NestedIterator {
    public:
        vector<ints::const_iterator> stack;
        vector<ints::const_iterator> stackIter;
        bool hasNext2;
        int nextN;
    
        NestedIterator(vector<NestedInteger> &nestedList) {
            stack.push_back(nestedList.cend());
            stackIter.push_back(nestedList.cbegin());
            hasNext2=false;
            getNext();
        }
    
        int next(){
            int oldNext = nextN;
            hasNext2 = false;
            getNext();
            return oldNext;
        }
    
        void getNext() {
            while(stackIter.size()){
                ints::const_iterator & iter = stackIter.back();
                if(iter ==  stack.back()){
                    stack.pop_back();
                    stackIter.pop_back();
                    continue;
                }
    
                const NestedInteger & last = *iter;
                iter++;
                if (!last.isInteger()){
                    stack.push_back(last.getList().cend());
                    stackIter.push_back(last.getList().cbegin());
                }
                else{
                    nextN = last.getInteger();
                    hasNext2 = true;
                    break;
                }
            }
        }
    
        bool hasNext() {
            return hasNext2;
        }
    };
    
    /**
     * Your NestedIterator object will be instantiated and called as such:
     * NestedIterator i(nestedList);
     * while (i.hasNext()) cout << i.next();
     */

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.