Google – Non Null Iterator

Google – Non Null Iterator
Input一个包含Null的iterator，wrap成一个Non-Null Iterator
[Solution]
Maintain a 'top' instance variable.
hasNext()的时候如果top不为null, 返回true。否则找到下一个不为null的为止，如果没有下一个了就返回false。
next()的时候直接返回top。但是这里要注意重置top为null，以便下一个hasNext()。
上面方法只要O(n)time和O(1)space。当然还有一种O(n) space的解法，把所有non-null element都存到一个list里面。

class Solution <T> implements Iterator<T> {

 

  Iterator<T> it;

  T top;

 

  public Solution(Iterator<T> it) {

    this.it = it;

  }

 

  @Override

  public T next() {

    T result = top;

    top = null;

    return result;

  }

 

  @Override

  public boolean hasNext() {

    if (top != null) {

      return true;

    }

 

    T curr = null;

    while (it.hasNext() && curr == null) {

      curr = it.next();

    }

    top = curr;

 

    return top != null;

  }

}

Read full article from Google – Non Null Iterator