摘要：方法直接查找數組的位的迭代器，調用方法得到的整數即為要返回的元素。再寫迭代器的方法返回指針元素的并讓指針通過遞歸方法指向下一個元素。

Given two 1d vectors, implement an iterator to return their elements alternately.

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

兩個一維向量，所以建立兩個Iterator。
要實現Zigzag交替迭代，可以用一個奇偶計數器count進行標記。
初始化：對兩個向量v1，v2調用iterator()方法，分別初始化為it1和it2；并將計數器置0.
next()方法：每次調用時先將計數器+1，若count為奇數或it2已迭代完，返回it1.next()；若count為偶數且it1已迭代完，返回it2.next()。 default返回-1。
hasNext()方法：只要it1或it2還有未迭代的元素，則返回true。

import java.util.Iterator;
public class ZigzagIterator {
    private Iterator it1;
    private Iterator it2;
    private int count;
    public ZigzagIterator(List v1, List v2) {
        this.it1 = v1.iterator();
        this.it2 = v2.iterator();
        count = 0;
    }

    public int next() {
        count++;
        if ((count % 2 == 1 && it1.hasNext()) || !it2.hasNext()) return it1.next();
        else if ((count % 2 == 0 && it2.hasNext()) || !it1.hasNext()) return it2.next();
        return -1;
    }

    public boolean hasNext() {
        return it1.hasNext() || it2.hasNext();
    }
}

Follow up Zigzag Iterator: What if you are given k 1d vectors? How well can your code be extended to such cases? 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".

Given k = 3 1d vectors:

[1,2,3]
[4,5,6,7]
[8,9]

Return [1,4,8,2,5,9,3,6,7].

對多個一維向量進行交叉的迭代操作，建立一個迭代器數組its和一個計位器index。
初始化：將迭代器數組初始化為ArrayList<>()，再將向量數組vecs循環使用迭代器并加入迭代器數組，然后將計位器初值設為0。
hasNext()方法：只要迭代器數組its.size()大于0，就返回true。
next()方法：直接查找its數組的index位的迭代器，調用next()方法得到的整數it即為要返回的元素。不過，找到it之后要先更新index：若當前迭代器不為空，index進行先+1后對its.size()取余的操作，指向下一個迭代器；若當前迭代器為空，從迭代器數組中remove這個迭代器，并對index進行對its.size()取余，刷新下個迭代器的位置。更新index后，返回取出的元素it。

public class ZigzagIterator2 {
    List> its;
    int index;
    public ZigzagIterator2(ArrayList> vecs) {
        this.its = new ArrayList>();
        //遍歷數組加入迭代器數組
        for (ArrayList vec: vecs) {
            if (vec.size() > 0) its.add(vec.iterator());
        }
        index = 0;
    }

    public int next() {
        int it = its.get(index).next();
        //刷新指針位置
        if (its.get(index).hasNext()) index = (index+1) % its.size();
        else {
            its.remove(index);
            if (its.size() > 0) index = index % its.size(); //注意這里要判斷its.size()不為0，才能取模
        }
        
        return it;
    }

    public boolean hasNext() {
        return its.size() > 0;
    }
}

Design an iterator over a binary search tree with the following rules:

Elements are visited in ascending order (i.e. an in-order traversal)
next() and hasNext() queries run in O(1) time in average.

For the following binary search tree, in-order traversal by using iterator is [1, 6, 10, 11, 12]

   10
 /    
1      11
        
  6       12

Extra memory usage O(h), h is the height of the tree.

Super Star: Extra memory usage O(1)

用stack對BST進行初始化：查找并加入所有左子樹結點。
next()方法：對stack.pop()的當前結點cur操作，存為temp，然后對cur.right進行查找左子樹結點并壓入stack的操作，最后返回原結點temp。
hasNext()方法：stack非空，則為true。

public class BSTIterator {
    Stack stack;
    public BSTIterator(TreeNode root) {
        stack = new Stack();
        while (root != null) {
            stack.push(root);
            root = root.left;
        }
    }

    public boolean hasNext() {
        return !stack.isEmpty();
    }
    
    public TreeNode next() {
        TreeNode cur = stack.pop();
        TreeNode temp = cur;
        if (cur.right != null) {
            cur = cur.right;
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
        }
        return temp;
    }
}

Given a nested list of integers, implement an iterator to flatten it.

Each element is either an integer, or a list -- whose elements may also be integers or other lists.

Given the list [[1,1],2,[1,1]], By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1].

Given the list [1,[4,[6]]], By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,4,6].

建立此種數據類型的迭代器iterator，和它的指針peek（初值為null）。
首先，要進行迭代的數據類型為NestedInteger，其實是一個樹狀的層級結構，可以用stack+recursion來做。
先寫一個迭代層級結構的遞歸方法iteratorNext()：
當迭代器非空--hasNext()，取出下一個元素next()，若此元素滿足isInteger()，就返回它；否則將外層的迭代器存入stack，而對當前元素繼續迭代和遞歸。
當迭代器為空--而stack非空，就pop出stack中的元素繼續遞歸。

再寫迭代器的next()方法：
返回指針元素的getInteger()；并讓指針通過遞歸方法指向下一個元素。

hasNext()方法：
指針元素不為空，就返回true。

import java.util.Iterator;
public class NestedIterator implements Iterator {
    private NestedInteger peek = null;
    private Iterator iterator;
    private Stack> stack = new Stack<>();
    public NestedIterator(List nestedList) {
        iterator = nestedList.iterator();
        peek = iteratorNext();
    }
    public NestedInteger iteratorNext() {
        if (iterator.hasNext()) {
            NestedInteger i = iterator.next();
            if (i.isInteger()) return i;
            else {
                stack.add(iterator);
                iterator = i.getList().iterator();
                return iteratorNext();
            }
        }
        else if (!stack.isEmpty()) {
            iterator = stack.pop();
            return iteratorNext();
        }
        else return null;
    }
    
    @Override
    public Integer next() {
        Integer next = peek.getInteger();
        peek = iteratorNext();
        return next;
    }
    
    @Override
    public boolean hasNext() {
        return peek != null;
    }
    
    @Override
    public void remove() {}
}

Given an Iterator class interface with methods: next() and hasNext(), design and implement a PeekingIterator that support the peek() operation -- it essentially peek() at the element that will be returned by the next call to next().

Here is an example. Assume that the iterator is initialized to the beginning of the list: [1, 2, 3].

Call next() gets you 1, the first element in the list.

Now you call peek() and it returns 2, the next element. Calling next() after that still return 2.

You call next() the final time and it returns 3, the last element. Calling hasNext() after that should return false.

Think of "looking ahead". You want to cache the next element.
Is one variable sufficient? Why or why not?
Test your design with call order of peek() before next() vs next() before peek().
For a clean implementation, check out Google"s guava library source code.

How would you extend your design to be generic and work with all types, not just integer?

略。

class PeekingIterator implements Iterator {
    public Iterator it;
    public Integer peek;
    public PeekingIterator(Iterator iterator) {
        // initialize any member here.
        this.it = iterator;
        if (it.hasNext()) peek = it.next();
        
    }

    // Returns the next element in the iteration without advancing the iterator.
    public Integer peek() {
        return peek;
    }

    // hasNext() and next() should behave the same as in the Iterator interface.
    // Override them if needed.
    @Override
    public Integer next() {
        Integer res = peek;
        peek = it.hasNext() ? it.next() : null;
        return res;
    }

    @Override
    public boolean hasNext() {
        return peek != null;
    }
}