Given two1dvectors, implement an iterator to return their elements alternately.

Have you met this question in a real interview?

Yes

Example

Given two 1d vectors:

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

By calling next repeatedly until hasNext returnsfalse, the order of elements returned by next should be:[1, 3, 2, 4, 5, 6].

1. 用余处判断在哪一个列表中取数，并且保持两个当前下标
2. 用2路归并两个头元素 (并且如果把2换做k可以不用变代码）

1.
public class ZigzagIterator {
    /*
    * @param v1: A 1d vector
    * @param v2: A 1d vector
    */
    private int index1, index2, count;
    List<Integer> l1, l2;
    public ZigzagIterator(List<Integer> v1, List<Integer> v2) {
        // do intialization if necessary
        index1 = 0;
        index2 = 0;
        l1 = v1;
        l2 = v2;
        count = 0;
    }

    /*
     * @return: An integer
     */
    public int next() {
        // write your code here
        if (index1 >= l1.size()) {
            return l2.get(index2++);
        }

        if (index2 >= l2.size()) {
            return l1.get(index1++);
        }

        if (count % 2 == 0) {
            count = 1 - count;
            return l1.get(index1++);
        }

        if (count % 2 == 1) {
            count = 1 - count;
            return l2.get(index2++);
        }

        return -1;

    }

    /*
     * @return: True if has next
     */
    public boolean hasNext() {
        // write your code here
        return index1 < l1.size() || index2 < l2.size();
    }
}

/**
 * Your ZigzagIterator object will be instantiated and called as such:
 * ZigzagIterator solution = new ZigzagIterator(v1, v2);
 * while (solution.hasNext()) result.add(solution.next());
 * Output result
 */

2.public class ZigzagIterator {
    /*
    * @param vecs: a list of 1d vectors
    */
    private List<List<Integer>> iterVecs;
    private Stack<Integer> stack;
    private int index;
    public ZigzagIterator(List<Integer> v1, List<Integer> v2) {
        // do intialization if necessary
        iterVecs = new ArrayList<>();
        iterVecs.add(v1);
        iterVecs.add(v2);
        index = 0;
        stack = new Stack<Integer>();
    }

    /*
     * @return: An integer
     */
    public int next() {
        // write your code here
        return stack.pop();
    }

    /*
     * @return: True if has next
     */
    public boolean hasNext() {
        // write your code here
        if (stack.isEmpty()) {
            for (int i = iterVecs.size() - 1; i >= 0; i--) {
                if (index < iterVecs.get(i).size()) {
                    stack.push(iterVecs.get(i).get(index));
                }
            }
            index++;
        }

        return !stack.isEmpty();
    }
}

/**
 * Your ZigzagIterator2 object will be instantiated and called as such:
 * ZigzagIterator2 solution = new ZigzagIterator2(vecs);
 * while (solution.hasNext()) result.add(solution.next());
 * Output result
 */