341. Flatten Nested List Iterator (Medium)

https://leetcode.com/problems/flatten-nested-list-iterator/

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].

Solutions

class NestedIterator implements Iterator<Integer> {

    // The major point of this solution is flatten the input List<NestedInteger> as
    // List<Integer> at first. Then process the flattened list when requests send in.

    int pointer = 0;

    List<Integer> flatten = new ArrayList<>();

    public NestedIterator(List<NestedInteger> nestedList) {
        if (nestedList == null || nestedList.size() == 0) {
            return;
        }

        for (int i = 0; i < nestedList.size(); i++) {
            recurse(nestedList.get(i));
        }
    }

    private void recurse(NestedInteger ni) {
        if (ni == null) {
            return;
        }

        // if ni is an integer
        if (ni.isInteger()) {
            flatten.add(ni.getInteger());

            return;
        }

        // if ni is a list
        for (NestedInteger itg : ni.getList()) {
            recurse(itg);
        }
    }

    @Override
    public Integer next() {
        if (hasNext()) {
            return flatten.get(pointer++);
        }

        return null;
    }

    @Override
    public boolean hasNext() {
        return pointer < flatten.size();
    }
}

Incorrect Solutions

References

Copyright © iovi.com 2017 all right reserved,powered by GitbookLast Modification: 2020-03-22 00:33:20

results matching ""

    No results matching ""