341 Flatten Nested List Iterator

1. Question

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

2. Implementation

思路:利用stack,从输入的Nested Integer List的后面逐个将List中的元素放到stack上
(1) hasNext(): 查看栈顶的元素是否Integer, 是的话直接返回true,否则栈顶元素代表一个list,pop出它,并展开这个list,从后面逐个将每个元素放在stack上
(2) next(): 用hasNext()判断是否还有下一个元素,如果有的话pop出stack的元素并且call getInteger(),否则return null
1
/**
2
* // This is the interface that allows for creating nested lists.
3
* // You should not implement it, or speculate about its implementation
4
* public interface NestedInteger {
5
*
6
* // @return true if this NestedInteger holds a single integer, rather than a nested list.
7
* public boolean isInteger();
8
*
9
* // @return the single integer that this NestedInteger holds, if it holds a single integer
10
* // Return null if this NestedInteger holds a nested list
11
* public Integer getInteger();
12
*
13
* // @return the nested list that this NestedInteger holds, if it holds a nested list
14
* // Return null if this NestedInteger holds a single integer
15
* public List<NestedInteger> getList();
16
* }
17
*/
18
public class NestedIterator implements Iterator<Integer> {
19
Stack<NestedInteger> stack = null;
20
21
public NestedIterator(List<NestedInteger> nestedList) {
22
stack = new Stack<>();
23
for (int i = nestedList.size() - 1; i >= 0; i--) {
24
stack.push(nestedList.get(i));
25
}
26
}
27
28
@Override
29
public Integer next() {
30
return stack.pop().getInteger();
31
}
32
33
@Override
34
public boolean hasNext() {
35
while (!stack.isEmpty()) {
36
NestedInteger curNI = stack.peek();
37
if (curNI.isInteger()) {
38
return true;
39
}
40
stack.pop();
41
42
for (int i = curNI.getList().size() - 1; i >= 0; i--) {
43
stack.push(curNI.getList().get(i));
44
}
45
}
46
return false;
47
}
48
}
49
50
/**
51
* Your NestedIterator object will be instantiated and called as such:
52
* NestedIterator i = new NestedIterator(nestedList);
53
* while (i.hasNext()) v[f()] = i.next();
54
*/
Copied!

3. Time & Space Complexity

时间和空间都是O(n)