Given a nested list of integers, implement an iterator to flatten it.
Each element is either an integer, or a list -- whose elements may also be integers or other lists.
Example 1:
Given the list
Given the list
[[1,1],2,[1,1]],
By calling next repeatedly until hasNext returns false, the order of elements returned by next should be:
[1,1,2,1,1].
Example 2:
Given the list
Given the list
[1,[4,[6]]],
By calling next repeatedly until hasNext returns false, the order of elements returned by next should be:
[1,4,6].
Solution:
Iterative: Stack
Use a stack to maintain all the flattened integer. If the current nestedInteger is a list, we push its elements(last->first) to the stack. Make sure all the elements in the stack are integers.
public class NestedIterator implements Iterator<Integer> {
Stack<NestedInteger> st;
public NestedIterator(List<NestedInteger> nestedList) {
st=new Stack<NestedInteger>();
for(int i=nestedList.size()-1;i>=0;i--){
st.push(nestedList.get(i));
}
}
@Override
public Integer next() {
return st.pop().getInteger();
}
@Override
public boolean hasNext() {
while(!st.empty() && !st.peek().isInteger()){
List<NestedInteger> li=st.pop().getList();
for(int i=li.size()-1;i>=0;i--){
st.push(li.get(i));
}
}
if(st.empty()) return false;
return true;
}
}
Another solution is kind of recursive solution. We recursively use the NestedIterator to iterate nested list. Backtrack to current list when the next iterator doesn't have next element.
public class NestedIterator implements Iterator<Integer> {
NestedIterator nextIt;
Iterator<NestedInteger> itr;
Integer nextInt;
public NestedIterator(List<NestedInteger> nestedList) {
itr=nestedList.iterator();
nextIt=null;
nextInt=null;
}
@Override
public Integer next() {
if(nextIt!=null) return nextIt.next();
return nextInt;
}
@Override
public boolean hasNext() {
if(nextIt!=null && nextIt.hasNext()) return true;
while(itr.hasNext()){
NestedInteger nextNestedInteger=itr.next();
nextIt=null;
if(nextNestedInteger.isInteger()){
nextInt=nextNestedInteger.getInteger();
return true;
}
else{
nextIt=new NestedIterator(nextNestedInteger.getList());
if(nextIt.hasNext()) return true;
}
}
return false;
}
}
