C++ solution using iterators and a stack. The solution is commented for ease of understanding.


  • 0
    G
    class NestedIterator {
    public:
    
        typedef vector<NestedInteger>::iterator Iter;
    
        vector<NestedInteger> List;
        vector<pair<Iter,Iter> > Stack;
        
        void HandleStack()
        {
            while(Stack.empty() == false)
            {
                //
                // first make sure that the begin iterator
                // is not at the end
                //
                
                if(Stack.back().first == Stack.back().second)
                {
                   Stack.pop_back();
                   
                   if(Stack.empty() == false)
                   {
                       Stack.back().first++;
                   }
                   
                   continue;
                }
               
                if(Stack.back().first->isInteger() == false)
                {
                    //
                    // important to declare Back as a reference to a vector !!!
                    //
                    
                    vector<NestedInteger> &Back = Stack.back().first->getList();
                    
                    if(Back.empty())
                    {
                        Stack.back().first++;
                    }
                    else
                    {
                        Stack.push_back(make_pair(Back.begin(),Back.end()));
                    }
                }
                else
                {
                    //
                    // break if we've reached an iterator that points to an integer
                    //
                    
                    break;
                }
            }
        }
        
        NestedIterator(vector<NestedInteger> &nestedList) 
        :
        List(nestedList)
        {
            if(nestedList.empty())
            {
                return;
            }
            
            Stack.push_back(make_pair(List.begin(),List.end()));
            HandleStack();
        }
    
        int next() 
        {
            int Val = Stack.back().first->getInteger();
            Stack.back().first++;
            HandleStack();
            return (Val);
        }
    
        bool hasNext() 
        {
            return (Stack.empty() == false);
        }
    };
    
    /**
     * 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.