Zigzag iterator

Array Design Queue Iterator

66.5% acceptance

Mar 31, 2026

710

Given two vectors of integers v1 and v2, implement an iterator to return their elements alternately. Implement the ZigzagIterator class: ZigzagIterator(List v1, List v2) initializes the object with the two vectors v1 and v2. boolean hasNext() returns true if the iterator still has elements, and false otherwise. int next() returns the current element of the iterator and moves the iterator to the next element.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

struct ZigzagIterator {
  data: Vec<Vec<i32>>,
  indices: Vec<usize>,
  turn: usize,
}

/** 
 * `&self` means the method takes an immutable reference.
 * If you need a mutable reference, change it to `&mut self` instead.
 */
impl ZigzagIterator {
  /** initialize your data structure here. */
  
  fn new(v1: Vec<i32>, v2: Vec<i32>) -> Self {
    ZigzagIterator {
      data: vec![v1, v2],
      indices: vec![0, 0],
      turn: 0,
    }
  }
  
  fn next(&mut self) -> i32 {
    let n = self.data.len();
    let mut attempts = 0;
    while attempts < n {
      let t = self.turn % n;
      if self.indices[t] < self.data[t].len() {
        let val = self.data[t][self.indices[t]];
        self.indices[t] += 1;
        self.turn = t + 1;
        return val;
      }
      self.turn = t + 1;
      attempts += 1;
    }
    unreachable!()
  }
  
  fn has_next(&self) -> bool {
    for i in 0..self.data.len() {
      if self.indices[i] < self.data[i].len() {
        return true;
      }
    }
    false
  }
}

// ZigzagIterator usage:
// let obj = ZigzagIterator::new(v1, v2);
// let ret_1: i32 = obj.next();
// let ret_2: bool = obj.has_next();