LeetCode 281: Zigzag Iterator

Explanation

To implement a Zigzag Iterator, we can use a queue to store the iterators of the given lists. We will iterate through each list in a round-robin manner, getting elements from each list in turn until all elements are exhausted.

1. Initialize a queue to store the iterators of the given lists.
2. Add non-empty lists' iterators to the queue.
3. While the queue is not empty, pop an iterator from the front of the queue, get the next element from it, and add the iterator back to the queue if it has more elements.
4. Repeat step 3 until all iterators are exhausted.

Time Complexity

• Initialization: O(n), where n is the number of lists.
• Getting next element: O(1) on average.
• Overall time complexity: O(N) where N is the total number of elements across all lists.

Space Complexity

• O(n) where n is the number of lists.

import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class ZigzagIterator {
    private Queue<Iterator<Integer>> queue;

    public ZigzagIterator(List<Integer> v1, List<Integer> v2) {
        queue = new LinkedList<>();
        if (!v1.isEmpty()) {
            queue.offer(v1.iterator());
        }
        if (!v2.isEmpty()) {
            queue.offer(v2.iterator());
        }
    }

    public int next() {
        Iterator<Integer> iter = queue.poll();
        int result = iter.next();
        if (iter.hasNext()) {
            queue.offer(iter);
        }
        return result;
    }

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