14. [Technical Interview] [Leetcode] - Flatten Nested List Iterator

The code won't compile because we don't know the implementation of NestedInteger, but we just need to fill in the NestedInterator constructor, the next() method and the hasNext() method. Will use a stack and will need to traverse backwards because we want to put the end elements in the stack first and the beginning elements in the stack last. This will result in the beginning elements showing up at the top of the stack (LIFO).

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81

import java.util.*; public class HelloWorld{ public static void main(String []args){ System.out.println("Hello World"); } /** * // This is the interface that allows for creating nested lists. * // You should not implement it, or speculate about its implementation * public interface NestedInteger { * * // @return true if this NestedInteger holds a single integer, rather than a nested list. * public boolean isInteger(); * * // @return the single integer that this NestedInteger holds, if it holds a single integer * // Return null if this NestedInteger holds a nested list * public Integer getInteger(); * * // @return the nested list that this NestedInteger holds, if it holds a nested list * // Return null if this NestedInteger holds a single integer * public List<NestedInteger> getList(); * } */ public class NestedIterator implements Iterator<Integer> { Stack<NestedInteger> stack = new Stack<NestedInteger>(); public NestedIterator(List<NestedInteger> nestedList) { // need to do traversal in reverse because we want the // last nested integer elements at the bottom of the stack // and the first nested integers at the top of the stack 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 current = stack.peek(); // if current is an integer and not a list of integer // return true and let next() take care of the popping if (current.isInteger()) { return true; } // else current is not an integer, so pop the list of integer off // then proceed to pushing each int in the current list of integer // to the stack, and let next() pop them later stack.pop(); // need to traverse in reverse because we want the last ints in the // nested integer to be at the bottom of the stack and the first ints // in the nested integer to be at the top of the stack for (int i = current.getList().size() - 1; i >= 0; i--) { stack.push(current.getList().get(i)); } } return false; } } /** * Your NestedIterator object will be instantiated and called as such: * NestedIterator i = new NestedIterator(nestedList); * while (i.hasNext()) v[f()] = i.next(); */ }