# 281. Zigzag Iterator

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

Example:

``````Input:
v1 = [1,2]
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].
``````

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:
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:

``````Input:
[1,2,3]
[4,5,6,7]
[8,9]

Output: [1,4,8,2,5,9,3,6,7].
``````

``````class ZigzagIterator {
public:
ZigzagIterator(vector<int>& v1, vector<int>& v2) {
v.push_back(v1);
v.push_back(v2);
i = j = 0;
}
int next() {
return i <= j ? v[0][i++] : v[1][j++];
}
bool hasNext() {
if (i >= v[0].size()) i = INT_MAX;
if (j >= v[1].size()) j = INT_MAX;
return i < v[0].size() || j < v[1].size();
}
private:
vector<vector<int>> v;
int i, j;
};
``````

``````class ZigzagIterator {
public:
ZigzagIterator(vector<int>& v1, vector<int>& v2) {
int n1 = v1.size(), n2 = v2.size(), n = max(n1, n2);
for (int i = 0; i < n; ++i) {
if (i < n1) v.push_back(v1[i]);
if (i < n2) v.push_back(v2[i]);
}
}
int next() {
return v[i++];
}
bool hasNext() {
return i < v.size();
}
private:
vector<int> v;
int i = 0;
};
``````

``````class ZigzagIterator {
public:
ZigzagIterator(vector<int>& v1, vector<int>& v2) {
if (!v1.empty()) q.push(make_pair(v1.begin(), v1.end()));
if (!v2.empty()) q.push(make_pair(v2.begin(), v2.end()));
}
int next() {
auto it = q.front().first, end = q.front().second;
q.pop();
if (it + 1 != end) q.push(make_pair(it + 1, end));
return *it;
}
bool hasNext() {
return !q.empty();
}
private:
queue<pair<vector<int>::iterator, vector<int>::iterator>> q;
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/281

Flatten 2D Vector

https://leetcode.com/problems/zigzag-iterator/

https://leetcode.com/problems/zigzag-iterator/discuss/71781/Short-Java-O(1)-space

https://leetcode.com/problems/zigzag-iterator/discuss/71779/Simple-Java-solution-for-K-vector

https://leetcode.com/problems/zigzag-iterator/discuss/71835/C%2B%2B-with-queue-(compatible-with-k-vectors)

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation