obsidian/АиСД/Задачи/LeetCode/Flatten Nested List Iterator.md

Leetcode #341 | #Medium | Рекурсия | Design

Идея

Заводим обычный лист и индекс. При next увеливаем индекс, перед этим отдав элемент. hasNext обычное сравнение index и list.size(). На старте вложенность убираем рекурсией. Внимательно надо изучить методы апишки.

Big-O

• Время O(N)
• Память O(N)

Код

public class NestedIterator implements Iterator<Integer> {
    private List<Integer> list = new ArrayList<>();
    private int idx = 0;
    public NestedIterator(List<NestedInteger> nestedList) { dfs(nestedList); }
    private void dfs(List<NestedInteger> nested) {
        for (NestedInteger el : nested) {
            if (el.isInteger()) list.add(el.getInteger());
            else dfs(el.getList());
        }
    }
    public Integer next() { return list.get(idx++); }
    public boolean hasNext() { return idx < list.size(); }
}