首页 > itarticle > zigzag iterator

zigzag iterator

admin 11月 11, 2020 0

Problem:

Given two 1d vectors, implement an iterator to return their elements alternately.

For example, given two 1d vectors:

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

分析

因为只有两个List，所以只要来回在两个迭代器之间切换就好了。思路比较简单，但是要考虑各种corner case。

public class  {
    private Iterator<Integer> iter1;
    private Iterator<Integer> iter2;
    private int exc;
    public (List<Integer> v1, List<Integer> v2) {
        if (v1 == null && v2 == null) return;
        this.iter1 = v1.iterator();
        this.iter2 = v2.iterator();
        this.exc = 1;
    }

    public int next() {
        Iterator<Integer> cur = null;
        if (!iter1.hasNext() && iter2.hasNext()) cur = iter2;
        if (!iter2.hasNext() && iter1.hasNext()) cur = iter1;
        if (iter1.hasNext() && iter2.hasNext()) {
            if (exc % 2 == 1) cur = iter1;
            else cur = iter2;
        }
        exc++;
        return cur.next();
    }

    public boolean hasNext() {
        return iter1.hasNext() || iter2.hasNext();
    }
}


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

follow-up。如果有多个List，其实只要用一个iterator的List就好了，可以实现在不同iterator之间的切换。