Sunday, October 16, 2016

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:
Given the list [[1,1],2,[1,1]],
By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1].
Example 2:
Given the list [1,[4,[6]]],
By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,4,6].

Use a stack, add all nestedInteger into the stack. Every time we see an integer, we pop it, otherwise we add all elements in the list into the stack.


public class NestedIterator implements Iterator {

    Stack stack = new Stack<>();

    public NestedIterator(List nestedIntegers) {
        for (int i = nestedIntegers.size() - 1; i >= 0; i--) {
            stack.push(nestedIntegers.get(i));
        }
    }

    @Override
    public Integer next() {
        if (!hasNext()) {
            return null;
        }

        return stack.pop().getInteger();
    }

    @Override
    public boolean hasNext() {
        while (!stack.isEmpty() && !stack.peek().isInteger()) {
            List list = stack.pop().getList();
            for (int i = list.size() - 1; i >= 0; i--) {
                stack.push(list.get(i));
            }
        }
        return !stack.isEmpty();
    }
}


Besides adding all elements into the stack, we can also add ListIterator of the list into the stack. From java doc:

An iterator for lists that allows the programmer to traverse the list in either direction, modify the list during iteration, and obtain the iterator's current position in the list. A ListIterator has no current element; its cursor positionalways lies between the element that would be returned by a call to previous() and the element that would be returned by a call to next(). An iterator for a list of length n has n+1 possible cursor positions, as illustrated by the carets (^) below: Element(0) Element(1) Element(2) ... Element(n-1)
cursor positions: ^ ^ ^ ^ ^
Note that the remove() and set(Object) methods are not defined in terms of the cursor position; they are defined to operate on the last element returned by a call to next() or previous().


public class NestedIterator implements Iterator {
    
    private Stack> list;
    
    public NestedIterator(List nestedList) {
        list = new Stack<>();
        list.add(nestedList.listIterator());
    }

    @Override
    public Integer next() {
        hasNext();
        return list.peek().next().getInteger();
    }

    @Override
    public boolean hasNext() {
        while(!list.empty()) {
            if(!list.peek().hasNext())
                list.pop();
            else {
                NestedInteger curr = list.peek().next();
                if (curr.isInteger())
                    return list.peek().previous() == curr;
                else
                    list.push(curr.getList().listIterator());
            }
        }
        return false;
    }
}


No comments:

Post a Comment