Flatten Nested List Iterator

 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:

Input: [[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: [1,[4,[6]]]
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].

Approach : Make a Flat List with Recursion
Intuition
The simplest way of solving this problem is to flatten the entire input list, in the constructor. Then the actual iterator methods can simply work with this flattened list instead of needing to worry about the input structure.
This approach splits the coding into two parts:
A function that the constructor can call to make a flattened list.
next() and hasNext() methods that iterate over a plain list, by keeping track of the current position within it.
The first part is best done with recursion (iteration is more complicated, and if you were going to use it, then you may as well look at approaches 2, 3, and 4 instead). This approach is the only recursive one that works in any programming language (as of the time of writing this article, things are changing!).
To flatten the list recursively, notice that we can look at the input as a tree. The integers are the leaf nodes, and the order they should be returned is from left to right.
Therefore, we can use a recursive depth-first search to flatten it.
integers = []

define function flattenList(nestedList):
    for nestedInteger in nestedList:
        if nestedInteger.isInteger():
            append nestedInteger.getInteger() to integers
        else:
            recursively call flattenList on nestedInteger.getList()
Program in Java
import java.util.NoSuchElementException;

public class NestedIterator implements Iterator<Integer> {
    
    private List<Integer> integers = new ArrayList<Integer>();
    private int position = 0; // Pointer to next integer to return.
    
    public NestedIterator(List<NestedInteger> nestedList) {
        flattenList(nestedList);
    }

    // Recursively unpacks a nested list in DFS order.
    private void flattenList(List<NestedInteger> nestedList) {
        for (NestedInteger nestedInteger : nestedList) {
            if (nestedInteger.isInteger()) {
                integers.add(nestedInteger.getInteger());
            } else {
                flattenList(nestedInteger.getList());
            }
        }
    }
    
    @Override
    public Integer next() {
        // As per Java specs, we should throw an exception if no more ints.
        if (!hasNext()) throw new NoSuchElementException();
        // Return int at current position, and then *after*, increment position.
        return integers.get(position++);
    }

    @Override
    public boolean hasNext() {
        return position < integers.size();
    }
}