Dada una lista anidada de enteros, implemente un iterador para aplanarla. Cada elemento es un número entero o una lista, cuyos elementos también pueden ser números enteros u otras listas.
Por ejemplo, dada la lista [[1,1], 2,[1,1]]llamando a next repetidamente hasta que hasNext devuelva falso, el orden de los elementos devueltos por next debería ser: [1,1,2,1,1].
Solución Java 1
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; } } |
Solución Java 2
public class NestedIterator implements Iterator<Integer> { Stack<Iterator<NestedInteger>> stack = new Stack<Iterator<NestedInteger>>(); Integer current; public NestedIterator(List<NestedInteger> nestedList) { if(nestedList==null) return; stack.push(nestedList.iterator()); } @Override public Integer next() { Integer result = current; current = null; return result; } @Override public boolean hasNext() { while(!stack.isEmpty() && current==null){ Iterator<NestedInteger> top = stack.peek(); if(!top.hasNext()){ stack.pop(); continue; } NestedInteger n = top.next(); if(n.isInteger()){ current = n.getInteger(); return true; }else{ stack.push(n.getList().iterator()); } } return false; } } |