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
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
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. AListIterator
has no current element; its cursor positionalways lies between the element that would be returned by a call toprevious()
and the element that would be returned by a call tonext()
. An iterator for a list of lengthn
hasn+1
possible cursor positions, as illustrated by the carets (^
) below: Element(0) Element(1) Element(2) ... Element(n-1)
cursor positions: ^ ^ ^ ^ ^
Note that theremove()
andset(Object)
methods are not defined in terms of the cursor position; they are defined to operate on the last element returned by a call tonext()
orprevious()
.
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