281. Zigzag Iterator

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

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].
4/11/2018 update:
Remember to check the v1 or v2 is empty case.

3/19/2018 update:

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

    public int next() {
        Iterator<Integer>  cur = queue.poll();
        int next = cur.next();
        if (cur.hasNext()) {
            queue.offer(cur);
        }
        return next;
    }

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

Analysis:
It is straight forward that we can use iterator for each list. But the tricky part is that how to roll the iterators, keep them swapping all the time. We need data structure to help. What comes in mind is Queue, first in first out and then in queue again. Another problem needs to be solved is how to eliminate empty iterator? If the current iterator.hasNext() == false, then don't add it to the queue again. This approach applies to unlimited number of lists.

Solution:

 public class ZigzagIterator {  
   Queue<Iterator<Integer>> queue = new LinkedList<>();  
   Iterator<Integer> cur = null;  
   public ZigzagIterator(List<Integer> v1, List<Integer> v2) {  
     queue.add(v1.iterator());  
     queue.add(v2.iterator());  
   }  
   public int next() {  
     return cur.next();  
   }  
   public boolean hasNext() {  
     while (!queue.isEmpty()) {  // check and removes all the empty iterators.
       cur = queue.remove();  
       if (cur.hasNext()) {  
         queue.add(cur);  
         break;  
       }  
     }  
   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();  
  */