Zigzag Iterator

LintCode Q 540 - Zigzag Iterator

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

Example1
Input: v1 = [1, 2] and v2 = [3, 4, 5, 6] ; Output: [1, 3, 2, 4, 5, 6]
Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1, 3, 2, 4, 5, 6].

Example2
Input: v1 = [1, 1, 1, 1] and v2 = [3, 4, 5, 6] ; Output: [1, 3, 1, 4, 1, 5, 1, 6]

Solution

Solution 1: Use two integer pointers

Code:

private pointer1, pointer2;
private List<Integer> list1, list2;
private boolean flag; // true: use pointer1, false: use pointer2

public ZigzagIterator(List<Integer> v1, List<Integer> v2) {
	list1 = new ArrayList<>(v1);
	list1 = new ArrayList<>(v2);
	pointer1 = 0; pointer2 = 0;
	flag = true;
}

public int next() {
	if (!hasNext()) return -1;

	if (flag) {
		flag = false;
		return list1.get(pointer1++);
	} else {
		flag = true;
		return list2.get(pointer2++);
	}

}


public boolean hasNext() {

	if (pointer1 < list1.size() || pointer2 < list2.size()) {
		if (pointer1 == list1.size()) flag = false;
		if (pointer2 == list2.size()) flag = true; 
		return true;
	}

	return false;

}

Solution 2: Use two iterators

Code:

private Iterator<Integer> iter1, iter2;
private int turns = 0;

public ZigzagIterator(List<Integer> v1, List<Integer> v2) {
	iter1 = v1.iterator();
	iter2 = v2.iterator();
}

public int next() {
	
	if (!hasNext()) return -1;

	turns++;
	if (turns % 2 == 1 && iter1.hasNext() || !iter2.hasNext()) {
		return iter1.next();
	} else if (turns % 2 == 0 && iter2.hasNext() || !iter1.hasNext()) {
		return iter2.next();
	}

	return -1;
}


public boolean hasNext() {
	return iter1.hasNext() || iter2.hasNext();
	

}