Simple Java 4ms O(1) space solution (with no other data structures besides the original lists).


  • 0

    The idea is quite straightforward. I use 2 integers curri and currj to record the position of the iterator. If the current position of the iterator is invalid when it is pointed to L1, move it to the L2 (Set currj = 1). If it happens to L2, move to L1 and move pointer of i ahead. (Set currj = 0 and curri++).
    I had some bugs for the hasNext function at the beginning. It is a little bit subtle. So take care of that function.
    For the general case of K lists, this method will also work. Before the last list is hit, check if the iterator have the right place to point to the current list, if yes, return the value, if no, move the next list. When the iterator cannot find the right place to point to the last list, move i ahead and get back to the first list.
    Here is my code. :)

    List<Integer> L1;
    List<Integer> L2;
    int curri;
    int currj;
    public ZigzagIterator(List<Integer> v1, List<Integer> v2) {
        L1 = v1;
        L2 = v2;
        curri = 0;
        currj = 0;
    }
    public int next() {
        while(curri<L1.size()||curri<L2.size()){
            if(currj==0){
                if(curri<L1.size()){
                    currj = 1;
                    return (int)L1.get(curri);
                }
                else{
                    currj = 1;
                }
            }
            else{
                if(curri<L2.size()){
                    currj  = 0;
                    curri += 1;
                    return (int)L2.get(curri-1);
                }
                else{
                    currj = 0;
                    curri+= 1;
                }
            }
        }
        return Integer.MAX_VALUE; //if this line is called, that means the hasNext function is wrong.
    }
    public boolean hasNext() {
        if(currj==0&&curri>=L1.size()){
            currj = 1;
            if(curri>=L2.size()){
                return false;
            }
        }
        if(currj==1&&curri>=L2.size()){
            curri +=1;
            currj = 0;
            if(curri>=L1.size()){
                return false;
            }
        }
        return true;
      }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.