Flatten Nested List Iterator(Medium)

interface NestedInteger {
    /**
     * @return true if this NestedInteger holds a single integer, rather than a
     *         nested list
     */
    boolean isInteger();

    /**
     * @return the single integer that this NestedInteger holds, if it holds a
     *         single integer Return null if this NestedInteger holds a nested
     *         list
     */
    Integer getInteger();

    /**
     * @return the nested list that this NestedInteger holds, if it holds a
     *         nested list Return null if this NestedInteger holds a single
     *         integer
     */
    List<NestedInteger> getList();
}

public class NestedIterator implements Iterator<Integer> {
    public NestedIterator(List<NestedInteger> nestedList) {
    it = nestedList.iterator();
}

@Override
public Integer next() {
    if (!components.isEmpty()) {
        return components.pop();
    } else {
        throw new NoSuchElementException();
    }
}

@Override
public boolean hasNext() {
    while (components.isEmpty() && it.hasNext()) {
        Stack<NestedInteger> stack = new Stack<NestedInteger>();
        stack.push(it.next());

        while (!stack.isEmpty()) {
            NestedInteger cur = stack.pop();

            if (cur.isInteger()) {
                components.push(cur.getInteger());
            } else if (cur.getList() != null) {
                for (NestedInteger ni : cur.getList()) {
                    stack.push(ni);
                }
            }
        }

    }

    return !components.isEmpty();
}

private Iterator<NestedInteger> it;
private Stack<Integer> components = new Stack<Integer>();
}

results matching ""

    No results matching ""