如何实现嵌套列表迭代器

Question

在一次采访中，我被问到这个问题：

“如何实现自定义嵌套列表迭代器？”

方法next（）应首先返回每个列表的第一个元素，然后再返回第二个元素，等等。

输入示例：

[[1,2,3],[4,5],[6],[],[7,8,9]]

输出：

[1,4,6,7,2,5,8,3,9]

stub-Code ：

public class CustomListIterator implements Iterator<Integer> {
    
    public CustomListIterator(List<List<Integer>> nestedList) {
        
    }

    @Override
    public boolean hasNext() {
        
    }
    
    @Override
    public Integer next() {
        
    }
}

如何实现？

Answer 1

您可以通过利用ListIterator和Iterator的组合来实现这一目标。这种方法使您可以摆脱保持任何立场的必要性。

一般的想法是创建迭代器的列表和 listiterator ，将在这些列表上迭代。

方法hasnext（）在列表上执行迭代，并检查它至少没有一个耗尽的迭代器。

方法next（）更精细。首先，它将尝试从列表的第一个元素之前的最后一个元素到位置的位置“重置” listiterator 。

然后在循环内，它将检查列表中的下一个迭代，如果此迭代器耗尽，则将被删除。为了使此操作快速，迭代器存储在linkedlist中。如果找到了元素，它将被返回。

为了处理“空”迭代器出现在列表末尾的情况， Listiterator 达到最后一个位置，但是列表中可能还有一些未访问的迭代器循环的结尾。

在下面的实现中，我在hasnext（）和构造函数中使用了流，以实现简洁的目的。即使您对流不太满意，总体逻辑也应该清除，并且可以轻松地用流来代替它。

public class CustomListIterator<T> implements Iterator<T> {
    private List<Iterator<T>> iterators;
    private ListIterator<Iterator<T>> listIterator;
    
    public CustomListIterator(List<List<T>> nestedList) {
        this.iterators = nestedList.stream()
            .map(List::iterator)
            .collect(Collectors.toCollection(LinkedList::new));
        
        this.listIterator = iterators.listIterator();
    }
    
    @Override
    public boolean hasNext() {        
        return iterators.stream().anyMatch(Iterator::hasNext);
    }
    
    @Override
    public T next() {
        if (!iterators.isEmpty() && !listIterator.hasNext()) tryReset();

        while (!iterators.isEmpty() && listIterator.hasNext()) {
            Iterator<T> current = listIterator.next();

            if (!current.hasNext()) {
                listIterator.remove(); // removing exhausted iterator
            } else {
                return current.next();
            }
    
            if (!listIterator.hasNext()) tryReset();
        }
        throw new IllegalStateException();
    }
    
    private void tryReset() {
        while (listIterator.hasPrevious()) {
            listIterator.previous();
        }
    }
}

main（） - 演示

public static void main(String[] args) {
    List<List<Integer>> numbers =
        List.of(List.of(1, 4, 6, 7),
                List.of(),
                List.of(2, 5),
                List.of(3));

    CustomListIterator<Integer> nestedIterator = new CustomListIterator<>(numbers);
    
    while (nestedIterator.hasNext()) {
        System.out.print(nestedIterator.next() + "\t");
    }
}

输出

1   2   3   4   5   6   7