# Question

Formatted question description: https://leetcode.ca/all/281.html

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

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

@tag-design


# Algorithm

### Extra space to save

Directly when class initialization, the two arrays are stored in another one-bit array in the order of zigzag, then the values in the new array are printed in order.

• need extra space

### No extra space

Use two variables i and j to record the current element positions of the two vectors, and initialize them to 0.

Then when i<=j, it means that you need to print the elements of v1 array, otherwise, print the elements of v2 array.

In the hasNext() function, when i or j is printed equal to the length of the corresponding array, assign it to an extra large value, which does not affect the printing of the value of the other array, only when i and j both exceed the length of the lattice array, return false.

Queue to hold a pair of iterators/indexes. During initialization, add iterator/index pairs and put them in the queue for every iterator. At initialization, each pair stores the the first and last index of the iterator.

In the next() function, take out a pair at the head of the queue. If the current iterator is not equal to end(), store the pari (iterator and the next index) to the queue, and then return the value at the current index.

In the hasNext() function, you only need to see if the queue is empty.

Java