281. Zigzag Iterator

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].

Follow up: What if you are given k 1d vectors? How well can your code be extended to such cases?

Clarification for the follow up question - Update (2015-09-18):
The "Zigzag" order is not clearly defined and is ambiguous for k > 2 cases. If "Zigzag" does not look right to you, replace "Zigzag" with "Cyclic". For example, given the following input:

[1,2,3]
[4,5,6,7]
[8,9]

It should return [1,4,8,2,5,9,3,6,7].



Solution:

The idea is to utilize a queue of Iterator.

Initially, we offer all non-empty lists' iterators into the queue.

The hasNext() simply check if the queue is not empty.

For each call of the next() function, we poll an iterators and call its own next() to retrieve a value.

If this iterator still hasNext(), we put it back into the end of the queue.



Code:

public class ZigzagIterator {

    public Queue<Iterator> queue;
    public ZigzagIterator(List<Integer> v1, List<Integer> v2) {
        queue = new LinkedList<>();
        if (v1.size() != 0) {
            queue.offer(v1.iterator());
        }
        if (v2.size() != 0) {
            queue.offer(v2.iterator());
        }
    }

    public int next() {
        hasNext();
        Iterator it = queue.poll();
        int val = (Integer)it.next();
        if (it.hasNext()) {
            queue.offer(it);
        }
        return val;
    }

    public boolean hasNext() {
        return !queue.isEmpty();
    }
}

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