题目及测试
package pid341; /* 扁平化嵌套列表迭代器 给你一个嵌套的整型列表。请你设计一个迭代器，使其能够遍历这个整型列表中的所有整数。 列表中的每一项或者为一个整数，或者是另一个列表。其中列表的元素也可能是整数或是其他列表。 示例 1: 输入: [[1,1],2,[1,1]] 输出: [1,1,2,1,1] 解释: 通过重复调用 next 直到 hasNext 返回 false，next 返回的元素的顺序应该是: [1,1,2,1,1]。 示例 2: 输入: [1,[4,[6]]] 输出: [1,4,6] 解释: 通过重复调用 next 直到 hasNext 返回 false，next 返回的元素的顺序应该是: [1,4,6]。 */ public class main { public static void main(String[] args) { } } package pid341; import java.util.Iterator; import java.util.List; 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 the nested list that this NestedInteger holds, if it holds a // nested list // Return null if this NestedInteger holds a single integer public List<NestedInteger> getList(); }解法1（成功，4ms，较快）
内部有一个stack，index大的先放进去，小的后放进去。next时，弹出最上面的，如果是数字，直接返回。如果不是数字，将列表从后到前依次放进stack，然后再次调用next方法。
hasNext，由于会出现stack不为空，但是NestInteger为{}的情况，需要先调用next得到返回的结果不为null，再返回true，同时把返回的结果放到nextInteger里面，next方法优先返回nextInteger，然后清空这个字段
package pid341; import java.util.Iterator; import java.util.List; import java.util.Stack; /** * // 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 the nested list that this NestedInteger holds, if it holds a nested list * // Return null if this NestedInteger holds a single integer * public List<NestedInteger> getList(); * } */ public class NestedIterator implements Iterator<Integer> { private Stack<NestedInteger> stack = new Stack<>(); // 如果调用了hasNext方法，会把下一次返回的结果存在里面，next方法会返回这个结果，并清空这个字段 Integer nextInteger = null; public NestedIterator(List<NestedInteger> nestedList) { if(nestedList.size() == 0){ return; } for(int i=nestedList.size()-1;i>=0;i--){ stack.push(nestedList.get(i)); } } @Override public Integer next() { if(nextInteger != null){ Integer result = nextInteger; nextInteger = null; return result; } if(stack.isEmpty()){ return null; } NestedInteger now = stack.pop(); if(now.isInteger()){ return now.getInteger(); }else{ List<NestedInteger> nestedList = now.getList(); if(nestedList.size() != 0){ for(int i=nestedList.size()-1;i>=0;i--){ stack.push(nestedList.get(i)); } } return next(); } } @Override public boolean hasNext() { if(stack.isEmpty()){ return false; }else{ Integer now = next(); if(now==null){ return false; }else{ nextInteger = now; return true; } } } } /** * Your NestedIterator object will be instantiated and called as such: * NestedIterator i = new NestedIterator(nestedList); * while (i.hasNext()) v[f()] = i.next(); */
解法2（别人的）
简单粗暴，在初始化迭代器的时候就直接把结果遍历出来，递归遍历列表中的数据，是整数就放入List，不是则再递归遍历，代码结构简单。
public class NestedIterator implements Iterator<Integer> { private List<Integer> list; private int index; public NestedIterator(List<NestedInteger> nestedList) { list = integerIterator(nestedList); index = -1; } @Override public Integer next() { if (this.hasNext()) return list.get(++index); return null; } @Override public boolean hasNext() { if (index + 1 < list.size()) return true; return false; } private static List<Integer> integerIterator(List<NestedInteger> nestedIntegerList) { ArrayList<Integer> list = new ArrayList<>(nestedIntegerList.size()); for (NestedInteger tmp : nestedIntegerList) { if (tmp.isInteger()) list.add(tmp.getInteger()); else list.addAll(integerIterator(tmp.getList())); } return list; } }解法3（别人的）
在类中添加nestedList、stack、iteratot、integer四个属性，分别对应嵌套列表、迭代器存储栈、当前迭代器、当前遍历整数
构造函数初始化nestedList、iterator，iterator对应的就是构造参数的迭代器。
重写hasNext()函数，主要逻辑为：
当前迭代器若hasNext()为true 判断next()是否为整数，若为整数则赋值integer，返回``true` 判断next()是否为列表，则将当前迭代器暂存至stack,并更新iterator为当前列表的迭代器，递归hasNext()函数
当前迭代器若hasNext()为false且stack非空，则迭代器出栈更新为当前iterator，递归hasNext()函数
其他情况则代表，整个扁平化嵌套列表已遍历完毕，返回false
重写next()函数，迭代器的使用规则是hasNext()返回为true时调用next()函数获取下一值，再次直接返回integer（当前遍历整数）即可。
public class NestedIterator implements Iterator<Integer> { //嵌套列表 private List<NestedInteger> nestedList = null; //迭代器存储栈 private Stack<Iterator<NestedInteger>> stack = new Stack<>(); //当前迭代器 private Iterator<NestedInteger> iterator = null; //当前遍历整数 private Integer integer = 0; public NestedIterator(List<NestedInteger> nestedList) { //嵌套列表初始化 this.nestedList = nestedList; iterator = nestedList.iterator(); } @Override public Integer next() { return integer; } @Override public boolean hasNext() { if(iterator.hasNext()) { NestedInteger nestedInteger = iterator.next(); if (!nestedInteger.isInteger()) { //该值为列表 stack.push(iterator); iterator = nestedInteger.getList().iterator(); return hasNext(); } else { integer = nestedInteger.getInteger(); return true; } }else if(!iterator.hasNext() && !stack.isEmpty()) { //当前迭代器至列表末尾并且栈非空 //迭代器更新为上一级 iterator = stack.pop(); return hasNext(); }else{ return false; } } }