|
11 | 11 | * public Integer getInteger(); |
12 | 12 | * |
13 | 13 | * // @return the nested list that this NestedInteger holds, if it holds a nested list |
14 | | - * // Returnnull if this NestedInteger holds a single integer |
| 14 | + * // Returnempty list if this NestedInteger holds a single integer |
15 | 15 | * public List<NestedInteger> getList(); |
16 | 16 | * } |
17 | 17 | */ |
18 | 18 | publicclassNestedIteratorimplementsIterator<Integer> { |
19 | | -List<NestedInteger>nestedList; |
20 | | -Queue<Integer>queue; |
21 | | -intidx; |
| 19 | + |
| 20 | +privateStack<NestedInteger>stack; |
| 21 | + |
22 | 22 | publicNestedIterator(List<NestedInteger>nestedList) { |
23 | | -this.nestedList =nestedList; |
24 | | -queue =newLinkedList<>(); |
25 | | -idx =0; |
26 | | -addToQueue(); |
| 23 | +stack =newStack<>(); |
| 24 | +for (inti =nestedList.size() -1;i >=0;i--) { |
| 25 | +stack.push(nestedList.get(i)); |
| 26 | +} |
27 | 27 | } |
28 | 28 |
|
29 | 29 | @Override |
30 | 30 | publicIntegernext() { |
31 | | -intval =queue.remove(); |
32 | | -if (queue.isEmpty()) { |
33 | | -if (idx !=nestedList.size()) { |
34 | | -addToQueue(); |
35 | | - } |
36 | | - } |
37 | | -returnval; |
38 | | - } |
39 | | - |
40 | | -privatevoidaddToQueue() { |
41 | | -while (idx <nestedList.size() &&queue.isEmpty()) { |
42 | | -addToQueueHelper(nestedList.get(idx++)); |
43 | | - } |
| 31 | +returnstack.pop().getInteger(); |
44 | 32 | } |
45 | 33 |
|
46 | | -privatevoidaddToQueueHelper(NestedIntegerns) { |
47 | | -if (ns.isInteger()) { |
48 | | -queue.add(ns.getInteger()); |
49 | | - } |
50 | | -else { |
51 | | -for (NestedIntegerni :ns.getList()) { |
52 | | -addToQueueHelper(ni); |
53 | | - } |
54 | | - } |
55 | | - } |
56 | | - |
57 | 34 | @Override |
58 | 35 | publicbooleanhasNext() { |
59 | | -return !(queue.isEmpty() &&idx ==nestedList.size()); |
| 36 | +while (!stack.isEmpty() && !stack.peek().isInteger()) { |
| 37 | +NestedIntegerpopped =stack.pop(); |
| 38 | +if (popped ==null) { |
| 39 | +continue; |
| 40 | + } |
| 41 | +List<NestedInteger>list =popped.getList(); |
| 42 | +for (inti =list.size() -1;i >=0;i--) { |
| 43 | +stack.push(list.get(i)); |
| 44 | + } |
| 45 | + } |
| 46 | +return !stack.isEmpty(); |
60 | 47 | } |
61 | 48 | } |
62 | 49 |
|
|