In this Leetcode Flatten Nested List Iterator problem solution, You are given a nested list of integers nestedList. Each element is either an integer or a list whose elements may also be integers or other lists. Implement an iterator to flatten it.

Implement the NestedIterator class:

  1. NestedIterator(List<NestedInteger> nestedList) Initializes the iterator with the nested list nestedList.
  2. int next() Returns the next integer in the nested list.
  3. boolean hasNext() Returns true if there are still some integers in the nested list and false otherwise.

Your code will be tested with the following pseudocode:

initialize iterator with nestedList

res = []

while iterator.hasNext()

    append iterator.next() to the end of res

return res

If res matches the expected flattened list, then your code will be judged as correct.

Leetcode Flatten Nested List Iterator problem solution


Problem solution in Python.

class NestedIterator(object):

    def __init__(self, nestedList):
        self.flatten_this_shit = list(reversed(list(self.flatten(nestedList))))
        
    def next(self):
        return self.flatten_this_shit.pop()
        
    def hasNext(self):
        return len(self.flatten_this_shit)
    
    def flatten(self, nestedList):
        for ni_outer in nestedList:
            if not ni_outer.isInteger():
                for ni_inner in self.flatten(ni_outer.getList()): yield ni_inner
            else: yield ni_outer.getInteger()



Problem solution in Java.

public class NestedIterator implements Iterator<Integer> {
    Queue<Integer> que;
    public NestedIterator(List<NestedInteger> nestedList) {
        que = new LinkedList<>();
        for(NestedInteger nest : nestedList) {
            if(nest.isInteger()) {
                que.offer(nest.getInteger());
            } else {
                help(nest.getList());
            }
        }
    }
    
    private void help(List<NestedInteger> n) {
        for(NestedInteger nest : n) {
            if(nest.isInteger()) {
                que.offer(nest.getInteger());
            } else {
                help(nest.getList());
            }
        }
    }

    @Override
    public Integer next() {
        if(hasNext()) return que.poll();
        else return null;
    }

    @Override
    public boolean hasNext() {
        return que.isEmpty() ? false : true;
    }
}


Problem solution in C++.

class NestedIterator {  
private:
    using Nested = vector<NestedInteger>;
    using IterPair = pair<Nested::iterator,Nested::iterator>; 
    
    Nested original;
    vector<IterPair> stack;
   
    void updateStack(){
        if(stack.empty()){
            return;
        }
        
        auto iterPair = stack.back();
        
        if(iterPair.first == iterPair.second){
            stack.pop_back();
            
            if(!stack.empty()){
                stack.back().first++;     
            }
        }else{
            if(iterPair.first->isInteger()){
                return;
            }
            
            auto &nested = iterPair.first->getList();
            stack.emplace_back(begin(nested),end(nested));
        }
        
        updateStack();
    }
    
public:
        
    NestedIterator(const vector<NestedInteger> &nestedList):original(nestedList){
        stack.emplace_back(begin(original),end(original));
        updateStack();
    }

    int next() {
        int ret = (stack.back().first->getInteger());
        stack.back().first++;
        updateStack();
        return ret;
    }

    bool hasNext() {
        return !stack.empty();
    }
};


Problem solution in C.

struct NestedIterator {
    struct NestedInteger** table;
    int index;

};

struct NestedIterator *nestedIterCreate(struct NestedInteger** nestedList, int nestedListSize) {

    struct NestedIterator* nestediterator = malloc(sizeof(struct NestedIterator));
    nestediterator -> table = malloc(sizeof(struct NestedInteger*)*1000);
    nestediterator -> index = nestedListSize - 1;

    for (int i = 0; i < nestedListSize; i++){
        nestediterator -> table[i] = nestedList[nestedListSize -1 -i];
    }

    return nestediterator;

}

bool nestedIterHasNext(struct NestedIterator *iter) {

    if ( iter -> index >= 0){
        while (!NestedIntegerIsInteger(iter -> table[ iter -> index])){
            struct NestedInteger** temp = NestedIntegerGetList(iter -> table[ iter -> index]);
            int size =  NestedIntegerGetListSize(iter -> table[ iter -> index]);
            if (iter -> index == 0 && size == 0){return 0;}
            for (int i = 0; i < size; i++){
                iter -> table[ iter -> index + i] = temp[size -1 -i];
            }
            iter -> index =  iter -> index + size - 1;
        }       
        return 1;
    }   
    return 0;
}

int nestedIterNext(struct NestedIterator *iter) {
    int temp = NestedIntegerGetInteger(iter -> table[ iter -> index]);
    iter -> index -=  1;
    return temp;
}

void nestedIterFree(struct NestedIterator *iter) {
    free(iter->table);
    free(iter);
}