跳转到主内容
极星编程网：以代码为星，赴技术山海！
📁 网站地图

怎么通过 for 循环实现对嵌套集合（List of List）的深度优先扁平化提取

苏承栈
苏承栈
• 👁 0人浏览过
深度优先扁平化嵌套List需用栈模拟递归：初始化栈并压入顶层列表，循环弹出元素，若为List则逆序压入其元素，否则加入结果；Java用ArrayDeque、Python用list实现，注意空值、循环引用及泛型擦除。 用 for 循环对嵌套 List（如
List>
）做深度优先扁平化，关键在于**模拟递归调用栈**：把待处理的子列表逐个压入栈，每次取出一个，遍历其元素——遇到普通元素就收集，遇到子列表就再压入栈。这样能保证“先深入再平铺”，符合深度优先顺序。 核心思路：用栈替代递归 深度优先不是靠“一层层 for 套 for”实现的（那只能处理固定层数），而是靠显式维护一个栈来记住“接下来该展开哪个子结构”。for 循环负责逐个处理栈顶，不关心嵌套有多深。 初始化一个栈（如
Stack
或
Deque
），把原始嵌套列表压入 循环直到栈为空：弹出一个元素 若它是目标类型（如
String
、
Integer
），直接加入结果列表 若它是
List
，则将其所有元素**逆序**压入栈（保证第一个子项最先被处理，维持 DFS 顺序） Java 示例：扁平化 List >（支持任意深度） 注意：这里用
ArrayDeque
模拟栈，用
instanceof
判断类型：
List flattenDFS(List nested) { List result = new ArrayList<>(); Deque stack = new ArrayDeque<>(); stack.push(nested); // 先压入顶层 
while (!stack.isEmpty()) {
    Object item = stack.pop();
    if (item instanceof List) {
        // 逆序压入，使 list.get(0) 成为下一个被 pop 的
        List list = (List) item;
        for (int i = list.size() - 1; i >= 0; i--) {
            stack.push(list.get(i));
        }
    } else {
        result.add(item);
    }
}
return result;
}
例如输入

[[1, [2, 3]], 4]

，输出为

[1, 2, 3, 4]

（深度优先：1 → 进入 [2,3] → 2 → 3 → 回退 → 4）。
Python 中用 list 模拟栈（同样 for 驱动）
Python 没有原生栈，但用

list.append()

和

list.pop()

可高效模拟：

def flatten_dfs(nested):
    result = []
    stack = [nested]  # 顶层入栈
    while stack:
        item = stack.pop()
        if isinstance(item, list):
            # 逆序扩展：让第一个元素最后进栈，最先出栈
            stack.extend(reversed(item))
        else:
            result.append(item)
    return result

调用

flatten_dfs([[1, [2, 3]], 4])

同样得

[1, 2, 3, 4]

。
注意事项与边界处理
实际使用时需考虑这些细节：
空值安全
：在压栈前检查

item != null

，避免

NullPointerException

或

TypeError

循环引用
：如果嵌套结构中存在自引用（如

a.add(a)

），需额外用

Set

记录已访问对象 ID，否则无限循环
泛型擦除
（Java）：运行时无法判断

List

还是

List

，所以统一用

Object

处理；若需强类型，可传入 Class
做运行时校验
性能提示
：频繁

push/pop

小对象开销低；若嵌套极深（万级层级），栈模拟比递归更安全，避免栈溢出
                            

                            
                            
                        
                    

                    
                    

                        
相关文章