## Algorithm

Problem Name: 341. Flatten Nested List Iterator

You are given a nested list of integers `nestedList`. Each element is either an integer or a list whose elements may also be integers or other lists. Implement an iterator to flatten it.

Implement the `NestedIterator` class:

• `NestedIterator(List<NestedInteger> nestedList)` Initializes the iterator with the nested list `nestedList`.
• `int next()` Returns the next integer in the nested list.
• `boolean hasNext()` Returns `true` if there are still some integers in the nested list and `false` otherwise.

Your code will be tested with the following pseudocode:

```initialize iterator with nestedList
res = []
while iterator.hasNext()
append iterator.next() to the end of res
return res
```

If `res` matches the expected flattened list, then your code will be judged as correct.

Example 1:

```Input: nestedList = [[1,1],2,[1,1]]
Output: [1,1,2,1,1]
Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1].
```

Example 2:

```Input: nestedList = [1,[4,[6]]]
Output: [1,4,6]
Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,4,6].
```

Constraints:

• `1 <= nestedList.length <= 500`
• The values of the integers in the nested list is in the range `[-106, 106]`.

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
struct NestedIterator {
int stack_sz;
int sp;
struct NestedInteger **stack;
int val;
};
​
#define PUSH(I, P) do { (I)->stack[(I)->sp ++] = (P); } while (0)
#define POP(I, P)  do { (P) = (I)->stack[-- (I)->sp]; } while (0)
​
struct NestedIterator *nestedIterCreate(struct NestedInteger** nestedList, int nestedListSize) {
struct NestedIterator *iter;
struct NestedInteger **stack, *p;
int i, sz;

sz = nestedListSize + 100;
stack = malloc(sz * sizeof(struct NestedInteger *));
iter = malloc(sizeof(struct NestedIterator));
//assert(stack && iter);
iter->stack_sz = sz;
iter->stack = stack;
iter->sp = 0;

while (nestedListSize > 0) {
p = nestedList[-- nestedListSize];
if (p) PUSH(iter, p);
}

return iter;
}
​
bool nestedIterHasNext(struct NestedIterator *iter) {
struct NestedInteger **list;
struct NestedInteger *p;
int n;

while (iter->sp) {
POP(iter, p);
if (NestedIntegerIsInteger(p)) {
//PUSH(iter, p);
iter->val = NestedIntegerGetInteger(p);
return true;
}
n = NestedIntegerGetListSize(p);
if (iter->sp + n >= iter->stack_sz) {
iter->stack_sz += n;
iter->stack = realloc(iter->stack, iter->stack_sz * sizeof(struct NestedInteger *));
//assert(iter->stack);
}
list = NestedIntegerGetList(p);
while (n > 0) {
p = list[-- n];
if (p) PUSH(iter, p);
}
}
return false;
}
​
int nestedIterNext(struct NestedIterator *iter) {
//printf("%d,", iter->val);
return iter->val;  // has next is always called prior
}
​
/** Deallocates memory previously allocated for the iterator */
void nestedIterFree(struct NestedIterator *iter) {
free(iter->stack);
free(iter);
}
``````
Copy The Code &

Input

cmd
nestedList = [[1,1],2,[1,1]]

Output

cmd
[1,1,2,1,1]

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
class NestedIterator {
public:
NestedIterator(vector<NestedInteger> &nestedList) {
this->nestedList = &nestedList;
}

int next() {
int n = q.front();
q.pop_front();
return n;
}

bool hasNext() {
while(q.empty() && i  <  nestedList->size()){
if((*nestedList)[i].isInteger())
q.push_back((*nestedList)[i].getInteger());
else{
NestedIterator* it = new NestedIterator((*nestedList)[i].getList());
while(it->hasNext()) q.push_back(it->next());
}
i++;
}
return !q.empty();
}

private:
vector < NestedInteger>* nestedList;
deque<int>q;
int i = 0;
};
``````
Copy The Code &

Input

cmd
nestedList = [[1,1],2,[1,1]]

Output

cmd
[1,1,2,1,1]

### #3 Code Example with Java Programming

```Code - Java Programming```

``````
public class NestedIterator implements Iterator {

private Stack stack;

public NestedIterator(List < NestedInteger> nestedList) {
this.stack = new Stack<>();
for (int i = nestedList.size() - 1; i >= 0; i--) {
this.stack.push(nestedList.get(i));
}
}

@Override
public Integer next() {
int value = this.stack.pop().getInteger();
return value;
}

@Override
public boolean hasNext() {
while (!this.stack.isEmpty() && !this.stack.peek().isInteger()) {
List < NestedInteger> ni = this.stack.pop().getList();
for (int i = ni.size() - 1; i >= 0; i--) {
this.stack.push(ni.get(i));
}
}
return !this.stack.isEmpty();
}
}
``````
Copy The Code &

Input

cmd
nestedList = [1,[4,[6]]]

Output

cmd
[1,4,6]

### #4 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
function flat(arr, res) {
for(let i = 0; i  <  arr.length; i++) {
if(arr[i].isInteger()) {
res.push(arr[i].getInteger())
} else {
flat(arr[i].getList() ,res)
}

}
}
const NestedIterator = function(nestedList) {
this.arr = []
this.idx = -1
flat(nestedList, this.arr)
};

NestedIterator.prototype.hasNext = function() {
return this.idx + 1 < this.arr.length
};

NestedIterator.prototype.next = function(> {
this.idx += 1
return this.arr[this.idx]
};
``````
Copy The Code &

Input

cmd
nestedList = [1,[4,[6]]]

Output

cmd
[1,4,6]

### #5 Code Example with C# Programming

```Code - C# Programming```

``````
using System;
using System.Collections.Generic;

namespace LeetCode
{
public class _0341_FlattenNestedListIterator
{
private Stack < NestedInteger> stack;

public _0341_FlattenNestedListIterator(IList nestedList)
{
this.stack = new Stack();
for (int i = nestedList.Count - 1; i >= 0; i--)
stack.Push(nestedList[i]);
}

public bool HasNext()
{
while (stack.Count > 0 && !stack.Peek().IsInteger())
{
var ni = stack.Pop();
var list = ni.GetList();
for (int i = list.Count - 1; i >= 0; i--)
stack.Push(list[i]);
}

return stack.Count > 0;
}

public int Next()
{
if (!HasNext()) throw new IndexOutOfRangeException();
return stack.Pop().GetInteger();
}

public class NestedInteger
{
private int? number;
private IList < NestedInteger> list;

public NestedInteger()
{
number = null;
list = new List < NestedInteger>();
}

public NestedInteger(int value)
{
number = value;
list = new List < NestedInteger>();
}

public bool IsInteger()
{
return number.HasValue;
}

public int GetInteger()
{
return number.Value;
}

public void SetInteger(int value)
{
number = value;
list = null;
}

{
number = null;
if (list == null)
list = new List < NestedInteger>() { ni };
else
}

public IList < NestedInteger> GetList()
{
return list;
}
}
}

}
``````
Copy The Code &

Input

cmd
nestedList = [[1,1],2,[1,1]]

Output

cmd
[1,1,2,1,1]