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

登录后复制

      
      

       
       /**
       
       
 * // This is the interface that allows for creating nested lists.
       
       
 * // You should not implement it, or speculate about its implementation
       
       
 * public interface NestedInteger {
       
       
 *
       
       
 *     // @return true if this NestedInteger holds a single integer, rather than a nested list.
       
       
 *     public 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
       
       
 *     public Integer getInteger();
       
       
 *
       
       
 *     // @return
       
       
public class NestedIterator implements Iterator<Integer> {
       
       

       
       
    Stack<Iterator<NestedInteger>> stk;
       
       
    Iterator<NestedInteger> tempIter;
       
       
    Integer temp = null;
       
       
    public NestedIterator(List<NestedInteger> nestedList) {
       
       
        stk = new Stack<Iterator<NestedInteger>>();
       
       
        tempIter = nestedList.iterator();
       
       
        temp = findNextInt();
       
       
    }
       
       

       
       
    @Override
       
       
    public Integer next() {
       
       
        int res = temp;
       
       
        temp = findNextInt();
       
       
        return res;
       
       
    }
       
       

       
       
    public Integer findNextInt() {
       
       
        while (tempIter.hasNext() || !stk.isEmpty()) {
       
       
            if (tempIter.hasNext()) {
       
       
                NestedInteger i = tempIter.next();
       
       
                if (i.isInteger()) {
       
       
                    return i.getInteger();
       
       
                } else {
       
       
                    stk.push(tempIter);
       
       
                    tempIter = i.getList().iterator();
       
       
                }
       
       
            } else {
       
       
                tempIter = stk.pop();
       
       
            }
       
       
        }
       
       
        return null;
       
       
    }
       
       

       
       
    @Override
       
       
    public boolean hasNext() {
       
       
        return temp != null;
       
       
    }
       
       
}
       
       

       
       
/**
       
       
 * Your NestedIterator object will be instantiated and called as such:
       
       
 * NestedIterator i = new NestedIterator(nestedList);
       
       
 * while (i.hasNext()) v[f()] = i.next();
       
       
 */
      
      
      
      

       
       
1.
       
       
2.
       
       
3.
       
       
4.
       
       
5.
       
       
6.
       
       
7.
       
       
8.
       
       
9.
       
       
10.
       
       
11.
       
       
12.
       
       
13.
       
       
14.
       
       
15.
       
       
16.
       
       
17.
       
       
18.
       
       
19.
       
       
20.
       
       
21.
       
       
22.
       
       
23.
       
       
24.
       
       
25.
       
       
26.
       
       
27.
       
       
28.
       
       
29.
       
       
30.
       
       
31.
       
       
32.
       
       
33.
       
       
34.
       
       
35.
       
       
36.
       
       
37.
       
       
38.
       
       
39.
       
       
40.
       
       
41.
       
       
42.
       
       
43.
       
       
44.
       
       
45.
       
       
46.
       
       
47.
       
       
48.
       
       
49.
       
       
50.
       
       
51.
       
       
52.
       
       
53.
       
       
54.
       
       
55.
       
       
56.
       
       
57.
       
       
58.
       
       
59.