> For the complete documentation index, see [llms.txt](https://aaronice.gitbook.io/lintcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://aaronice.gitbook.io/lintcode/data_structure/flatten-nested-list-iterator.md).

# Flatten Nested List Iterator

`Stack`, `Design`

**Medium**

Given a nested list of integers, implement an iterator to flatten it.

Each element is either an integer, or a list -- whose elements may also be integers or other lists.

**Example 1:**

```
Input: [[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: [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].
```

## Solution

### Stack

Similar to Nested List Weight Sum, we can use recursion to solve it. But since we need to access each **NestedInteger** at a time, we will use a stack to help.

In the constructor, we push all the **nestedList** into the **stack** from back to front, so when we **pop** the stack, it returns the very first element.

Second, in the `hasNext()` function, we peek the first element in stack currently, and if it is an Integer, we will return true and pop the element. If it is a list, we will further **flatten** it. This is iterative version of flatting the nested list. Again, we need to iterate from the back to front of the list.

```java
public class NestedIterator implements Iterator<Integer> {

    private Stack<NestedInteger> stack;

    public NestedIterator(List<NestedInteger> nestedList) {
        stack = new Stack<>();
        flattenList(nestedList);
    }

    @Override
    public Integer next() {
        return hasNext() ? stack.pop().getInteger() : null;
    }

    @Override
    public boolean hasNext() {
        while (!stack.isEmpty()) {
            if (stack.peek().isInteger()) return true;
            flattenList(stack.pop().getList());
        }
        return false;
    }

    private void flattenList(List<NestedInteger> list) {
        for (int i = list.size() - 1; i >= 0; i--) {
            stack.push(list.get(i));
        }
    }
}
```

### Pre-populate - Using Queue to Store - Recursive

```java
public class NestedIterator implements Iterator<Integer> {

    private Queue<Integer> queue = new LinkedList();

    public NestedIterator(List<NestedInteger> nestedList) {
        helper(nestedList);
    }

    private void helper(List<NestedInteger> list){
        if (list == null) {
            return;   
        }

        for (NestedInteger in: list){
            if (in.isInteger())
                queue.offer(in.getInteger());
            else {
                helper(in.getList());
            }
        }
    }

    @Override
    public Integer next() {
        if (hasNext()) {
            return queue.poll();
        } else {
            return -1;
        }
    }

    @Override
    public boolean hasNext() {
        if (!queue.isEmpty()) {
            return true;
        } else {
            return false;
        }
    }
}
```

### 预先全部flatten - Recursive

```java
class NestedIterator implements Iterator<Integer> {

    Iterator<Integer> iterator;

    public NestedIterator(List<NestedInteger> nestedList) {
        List<Integer> nums = new ArrayList<>();
        if(nestedList != null) {
            flatten(nestedList,nums);
        }
        iterator = nums.iterator();
    }

    private void flatten(List<NestedInteger> nestedList, List<Integer> nums) {
        for(NestedInteger n : nestedList) {
            if(n.isInteger()) {
                nums.add(n.getInteger());
            } else {
                flatten(n.getList(),nums);
            }
        }
    }

    @Override
    public Integer next() {
        return iterator.next();
    }

    @Override
    public boolean hasNext() {
        return iterator.hasNext();
    }
}
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://aaronice.gitbook.io/lintcode/data_structure/flatten-nested-list-iterator.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.