## 281. Zigzag Iterator

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

Example:

``````Input:
v1 = [1,2]
v2 = [3,4,5,6]

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

Explanation: 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?

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:

``````Input:

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

Output: [1,4,8,2,5,9,3,6,7].
``````

Code: Python Generator

``````class ZigzagIterator(object):

def __init__(self, v1, v2):
"""
:type v1: List[int]
:type v2: List[int]
"""
self.vals = (v[i] for i in itertools.count() for v in (v1, v2) if i < len(v))
self.n = len(v1) + len(v2)

def next(self):
"""
:rtype: int
"""
self.n -= 1
return next(self.vals)

def hasNext(self):
"""
:rtype: bool
"""
return self.n > 0

# Your ZigzagIterator object will be instantiated and called as such:
# i, v = ZigzagIterator(v1, v2), []
# while i.hasNext(): v.append(i.next())
``````

Code: Java k vectors

``````public class ZigzagIterator {
public ZigzagIterator(List<Integer> v1, List<Integer> v2) {
if(!v1.isEmpty())
if(!v2.isEmpty())
}

public int next() {
Iterator iter = queue.remove(); //
int ret = (Integer)iter.next();
return ret;
}

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();
*/
``````

C++ Iterator < start: end> pairs

``````class ZigzagIterator {
public:
ZigzagIterator(vector<int>& v1, vector<int>& v2) {
if(!v1.empty())  q.push(make_pair(v1.begin(), v1.end()));
if(!v2.empty())  q.push(make_pair(v2.begin(), v2.end()));
}

int next() {
auto i = q.front().first;
auto end = q.front().second;
q.pop();
if(i + 1 != end) q.push(make_pair(i + 1, end));

return *i;
}

bool hasNext() {
return !q.empty();
}
private:
queue<pair<vector<int>:: iterator, vector<int>:: iterator>> q;
};

/**
* Your ZigzagIterator object will be instantiated and called as such:
* ZigzagIterator i(v1, v2);
* while (i.hasNext()) cout << i.next();
*/
``````