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 givenk1d vectors? How well can your code be extended to such cases?

Clarificationfor the follow up question: The "Zigzag" order is not clearly defined and is ambiguous fork > 2cases. 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):
        """
        Initialize your data structure here.
        :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 {
    LinkedList<Iterator> queue;
    public ZigzagIterator(List<Integer> v1, List<Integer> v2) {
        queue = new LinkedList();
        if(!v1.isEmpty())
           queue.add(v1.iterator());
        if(!v2.isEmpty())
            queue.add(v2.iterator());
    }

    public int next() {
        Iterator iter = queue.remove(); //
        int ret = (Integer)iter.next();
        if(iter.hasNext()) queue.add(iter);
        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();
 */