Sponsored
Sponsored
This approach utilizes recursion to flatten the nested list. The idea is to traverse each element in the nested list. If the element is an integer, it gets added to a result list. If it's a list, the function calls itself recursively to add its flattened elements to the result list.
Time Complexity: O(N), where N is the total number of integers in the nested list. Space Complexity: O(N) for the flattened list storage.
1public class NestedIterator implements Iterator<Integer> {
2 private List<Integer> flatList;
3 private int index;
4
5 public NestedIterator(List<NestedInteger> nestedList) {
6 flatList = new ArrayList<>();
7 index = 0;
8 flatten(nestedList);
9 }
10
11 private void flatten(List<NestedInteger> nestedList) {
12 for (NestedInteger element : nestedList) {
13 if (element.isInteger()) {
14 flatList.add(element.getInteger());
15 } else {
16 flatten(element.getList());
17 }
18 }
19 }
20
21 public Integer next() {
22 return flatList.get(index++);
23 }
24
25 public boolean hasNext() {
26 return index < flatList.size();
27 }
28}In Java, a similar recursive approach is employed. The `flatList` holds the flattened integers, and `index` tracks the iteration. The `hasNext` and `next` methods facilitate list traversal.
This approach uses a stack to iterate over the nested list in a depth-first manner. This helps simulate recursive behavior iteratively, thus allowing the use of iterator pattern directly without full pre-flattening.
Time Complexity: Amortized O(1) per call for `next` and `hasNext` due to efficient stack management. Space Complexity: O(N), where N is the total number of integers stored in the stack during traversal.
1class NestedIterator {
2 constructor(nestedList
The implementation utilizes a stack to simulate recursive traversal. The stack is populated in reverse order to ensure elements are visited in correct sequence. The `hasNext` method ensures the top of the stack is an integer before processing.