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

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


我的想法是维护(r,c)这个坐标，用一个list来存。在询问hasNext的时候需要注意！判断从这行往下能不能行，当走到底的时候，还要看从上头再下来能不能行。

 public class ZigzagIterator {  
   int r;  
   int c;  
   List<List<Integer>> list;  
   public ZigzagIterator(List<Integer> v1, List<Integer> v2) {  
     list = new ArrayList<>();  
     list.add(v1);  
     list.add(v2);  
     r= 0;c=0;  
   }  
   public int next() {  
     return list.get(r++).get(c);  
   }  
   public boolean hasNext() {  
     while(r < list.size() && list.get(r).size() <= c){  
       r++;  
     }  
     if(r == list.size()) {c++;r=0;}  
     while(r < list.size() && list.get(r).size() <= c){  
       r++;  
     }  
     return r!=list.size() && c < list.get(r).size();  
   }  
 }  

Better Solution

用linkedlist来做，这样拆list的cost只有O(1)，每次把头拆下来，看一下能不能加到尾巴上就可以了。

next, hasNext 都是O(1)

Uses a linkedlist to store the iterators in different vectors. Every time we call next(), we pop an element from the list, and re-add it to the end to cycle through the lists.

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

    public int next() {
        Iterator poll = list.remove();
        int result = (Integer)poll.next();
        if(poll.hasNext()) list.add(poll);
        return result;
    }

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