SuperIterator.java

class IteratorWrapper implements Iterator<String> {
    private Iterator<?> i1;
    private Iterator<?> i2;
    private String value;

    IteratorWrapper(Iterator<?> iterator) {
        this.i1 = iterator;
        this.i2 = Collections.emptyIterator();
    }

    private IteratorWrapper(Iterator<?> i1, Iterator<?> i2) {
        this.i1 = i1;
        this.i2 = i2;
    }

    @Override
    public boolean hasNext() {
        if (value != null)
            return true;

        while (i1.hasNext()) {
            Object v = i1.next();
            if (v instanceof String) {
                value = v.toString();
                return true;
            } else if (v instanceof Iterator) {
                i1 = new IteratorWrapper((Iterator<?>) v, i1);
            } else
                throw new IllegalArgumentException("I don't know what it's");
        }

        while (i2.hasNext()) {
            Object v = i2.next();
            if (v instanceof String) {
                value = v.toString();
                return true;
            } else if (v instanceof Iterator) {
                i2 = new IteratorWrapper((Iterator<?>) v, i2);
            } else
                throw new IllegalArgumentException("I don't know what it's");
        }

        return false;
    }

    @Override
    public String next() {
        String result = this.value;
        this.value = null;
        return result;
    }
}

public class Solution {
    public static void main(String[] args) {
        Iterator iterator = Arrays.asList(
                Arrays.asList("1", "2", Arrays.asList("3").iterator()).iterator(),
                "4", "5",
                Arrays.asList(Arrays.asList("6", Arrays.asList("7", "8").iterator()).iterator(), "9").iterator()
        ).iterator();

        IteratorWrapper wrapper = new IteratorWrapper(iterator);
        while (wrapper.hasNext())
            System.out.println(wrapper.next());
    }
}