Most of other shared solutions are not correct


  • 0

    An iterator generally contains 3 operations - increment, retrieve, termination test
    However the given template has only two - next(), hasNext()
    By definition, next() retrieves the next value while hasNext() tests the termination. The increment operation is not mentioned and most people assume that hasNext() should do this. IMHO, if we have to choose between the two, next() is definitely a better place as the name of hasNext() implies that it is only a test.
    This usually means that hasNext() does not change any data state (i.e. const function in c++) and that consecutive next() calls return different data even without calling hasNext(). Most of the posted solutions don't have such a behavior.

    My solution for reference:

    class NestedIterator {
        stack<NestedInteger*> st;
        
        void locateNext() {
            while (!st.empty()) {
                auto &ni = *st.top();
                if (ni.isInteger())
                    return;
                st.pop();
                auto &list = ni.getList();
                for (auto p = list.rbegin(); p != list.rend(); p++)
                    st.emplace(&*p);
            }
        }
    
    public:
        NestedIterator(vector<NestedInteger> &list) {
            for (auto p = list.rbegin(); p != list.rend(); p++)
                st.emplace(&*p);
            locateNext();
        }
        
        int next() {
            int val = st.top()->getInteger();
            st.pop();
            locateNext();
            return val;
        }
    
        bool hasNext() const {
            return !st.empty();
        }
    };
    

Log in to reply
 

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