Zigzag Iterator

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

For example, given two 1d vectors:

v1 = [1, 2] v2 = [3, 4, 5, 6]By calling

nextrepeatedly untilhasNextreturns`false`

, the order of elements returned bynextshould 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 – Update (2015-09-18):

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, given the following input:[1,2,3] [4,5,6,7] [8,9]It should return

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

.

Keep the invariant in mind.

//invariant keep row, col always points to next available element class ZigzagIterator { public: vector<vector<int>> data; int row, col; bool isEnd; ZigzagIterator(vector<int>& v1, vector<int>& v2) { data.push_back(v1); data.push_back(v2); row = col = 0; isEnd = false; while(row < data.size() && data[row].size() == 0){ row++; } if(row == data.size()){ isEnd = true; } } int next() { int ans = data[row][col]; row++; while(row < data.size() && data[row].size() <= col){ row++; } if(row == data.size()){ row = 0; col++; } while(row < data.size() && data[row].size() <= col){ row++; } if(row == data.size()){ isEnd = true; } return ans; } bool hasNext() { return !isEnd; } }; /** * Your ZigzagIterator object will be instantiated and called as such: * ZigzagIterator i(v1, v2); * while (i.hasNext()) cout << i.next(); */