A solution using stacks


  • 0
    A

    The key is to find the next integer. If we encountered a list, push it to stack, record the index and start over.

    public class NestedIterator {
        private Stack<IList<NestedInteger>> pastLists = new Stack<IList<NestedInteger>>();
        private Stack<int> pastIndices = new Stack<int>();
        private IList<NestedInteger> curList;
        private int curIndex;
    
        public NestedIterator(IList<NestedInteger> nestedList) {
            pastLists = new Stack<IList<NestedInteger>>();
            pastIndices = new Stack<int>();
            curList = nestedList;
            curIndex = -1;
        }
    
        public bool HasNext() {
            return findNextInt();
        }
    
        public int Next() {
            return curList[curIndex].GetInteger();
        }
        
        private bool findNextInt(){
            curIndex++;
            if (curIndex>=curList.Count){
                if (pastLists.Count==0){
                    return false;  // no more elements
                }
                curList = pastLists.Pop();
                curIndex = pastIndices.Pop();
                return findNextInt();
            }
            if (curList[curIndex].IsInteger()){
                return true;
            }
            pastLists.Push(curList);
            pastIndices.Push(curIndex);
            curList = curList[curIndex].GetList();
            curIndex = -1;
            return findNextInt();
        }
    }

Log in to reply
 

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