top of page
Search

# Flatten Nested List Iterator

Updated: Apr 14, 2021

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:

• NestedIterator(List<NestedInteger> nestedList) Initializes the iterator with the nested list nestedList.

• int next() Returns the next integer in the nested list.

• boolean hasNext() Returns true if there are still some integers in the nested list and false otherwise.

Example 1:

```Input: nestedList = [[1,1],2,[1,1]]
Output: [1,1,2,1,1]
Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1].

```

Example 2:

```Input: nestedList = [1,[4,]]
Output: [1,4,6]
Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,4,6].

```

Constraints:

• 1 <= nestedList.length <= 500

• The values of the integers in the nested list is in the range [-106, 106].

Solution:

```public class NestedIterator implements Iterator<Integer> {
Stack<NestedInteger> stack = new Stack<NestedInteger>();

public NestedIterator(List<NestedInteger> nestedList) {
if(nestedList==null)
return;

for(int i=nestedList.size()-1; i>=0; i--){
stack.push(nestedList.get(i));
}
}

@Override
public Integer next() {
return stack.pop().getInteger();
}

@Override
public boolean hasNext() {
while(!stack.isEmpty()){
NestedInteger top = stack.peek();
if(top.isInteger()){
return true;
}else{
stack.pop();
for(int i=top.getList().size()-1; i>=0; i--){
stack.push(top.getList().get(i));
}
}
}

return false;
}

}```