251. Flatten 2D Vector

Description

Implement an iterator to flatten a 2d vector.

For example,
Given 2d vector =

[
[1,2],
[3],
[4,5,6]
]

By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,2,3,4,5,6].

Follow up:
As an added challenge, try to code it using only iterators in C++ or iterators in Java.

Solution

Iteration, hasNext time O(n), next() time O(1), space O(1)

乍一看感觉是简单题，后来发现有坑，考虑List中有空的情况，例如[[]]，或者[[1], [], [2]]，同一时刻hasNext()可能会返回true，但是next()会抛异常。所以必须在hasNext()中定位到下一个元素，next()里面调用hasNext()然后将元素输出即可。

public class Vector2D implements Iterator<Integer> {

    private Iterator<List<Integer>> i;
    private Iterator<Integer> j;
    
    public Vector2D(List<List<Integer>> vec2d) {
        i = vec2d.iterator();
    }

    @Override
    public Integer next() {
        hasNext();  // important
        return j.next();
    }

    @Override
    public boolean hasNext() {
        while (i.hasNext() && (j == null || !j.hasNext())) {  // tricky
                j = i.next().iterator();
        }
        
        return j != null && j.hasNext();
    }
}

/**
 * Your Vector2D object will be instantiated and called as such:
 * Vector2D i = new Vector2D(vec2d);
 * while (i.hasNext()) v[f()] = i.next();
 */