方法1: 这道题目其实251题的简易版，所以自然方法是一模一样的。方法1是将两个链表整合成1个链表。这是最简单容易想到的方法。

public class ZigzagIterator {
    List<Integer> list = new ArrayList<>();
    
    int count = 0;
    public ZigzagIterator(List<Integer> v1, List<Integer> v2) {
        boolean flag = true;
        int p1 = 0;
        int p2 = 0;
        while(p1 < v1.size() || p2 < v2.size()){
            if(p1 >= v1.size()){
                list.add(v2.get(p2));
                p2++;
            }else if(p2 >= v2.size()){
                list.add(v1.get(p1));
                p1++;
            }else if(flag && p1 < v1.size()){
                list.add(v1.get(p1));
                p1++;
                flag = false;
            }else if(!flag && p2 < v2.size()){
                list.add(v2.get(p2));
                p2++;
                flag = true;
            }
        }
    }

    public int next() {
        int res = list.get(count);
        count++;
        return res;
    }

    public boolean hasNext() {
        return count < list.size();
    }
}

/**
 * Your ZigzagIterator object will be instantiated and called as such:
 * ZigzagIterator i = new ZigzagIterator(v1, v2);
 * while (i.hasNext()) v[f()] = i.next();
 */

方法2: two pointer。两个pointer定位当前指向的数字。整个过程中移动两个pointer以找到下一个数字的位置。

public class ZigzagIterator {
    int row;
    int col;
    List<Integer> v1;
    List<Integer> v2;
    public ZigzagIterator(List<Integer> v1, List<Integer> v2) {
        this.row = 0;
        this.col = 0;
        this.v1 = v1;
        this.v2 = v2;
    }

    public void beforeNext(){
        if(row == 0 && col >= v1.size()){
            row++;
        }
        if(row == 1 && col >= v2.size()){
            row--;
            col++;
        }
    }
    public int next() {
        if(row == 0){
            row++;
            return v1.get(col); 
        }else{
            int res = v2.get(col);
            row--;
            col++;
            return res;
        }
    }

    public boolean hasNext() {
        beforeNext();
        return col < Math.max(v1.size(), v2.size());
    }
}

/**
 * Your ZigzagIterator object will be instantiated and called as such:
 * ZigzagIterator i = new ZigzagIterator(v1, v2);
 * while (i.hasNext()) v[f()] = i.next();
 */

总结：

• 无