Java中如何高效利用LinkedList生成元素插入所有索引的嵌套列表？

思路分析 #

原列表长度为n时，可插入0的位置共有n+1个（从索引0到索引n）。我们只需要遍历每个插入位置，基于原列表创建新列表并插入0，最后将所有新列表收集起来即可。整体时间复杂度为O(n²)，这是该问题的最优复杂度——毕竟最终结果总共有(n+1)²个元素，必须完成这么多次操作。

方式一：基础循环实现（直观高效） #

这种方式代码清晰，性能稳定，适合大多数场景：

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Arrays;

public class InsertZeroDemo {
    public static void main(String[] args) {
        List<Integer> list = new LinkedList<>(Arrays.asList(1, 2, 3));
        List<List<Integer>> result = new ArrayList<>();
        
        // 遍历所有可插入的位置：0到list.size()（共list.size()+1个位置）
        for (int i = 0; i <= list.size(); i++) {
            // 用ArrayList做临时列表更适合随机插入操作，性能比LinkedList更稳定
            List<Integer> temp = new ArrayList<>(list);
            temp.add(i, 0);
            result.add(temp);
        }
        
        System.out.println(result); // 输出目标结果：[[0, 1, 2, 3], [1, 0, 2, 3], [1, 2, 0, 3], [1, 2, 3, 0]]
    }
}

小提示：这里选ArrayList而非原列表的LinkedList做临时容器，是因为LinkedList的指定位置插入需要先遍历到对应索引，实际性能反而不如ArrayList在这种场景下的表现。

方式二：Stream流实现（简洁优雅） #

如果偏好函数式编程风格，Java 8+的Stream可以让代码更简洁，性能和循环方式不相上下：

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Arrays;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class InsertZeroStreamDemo {
    public static void main(String[] args) {
        List<Integer> list = new LinkedList<>(Arrays.asList(1, 2, 3));
        
        List<List<Integer>> result = IntStream.rangeClosed(0, list.size())
                .mapToObj(i -> {
                    List<Integer> temp = new ArrayList<>(list);
                    temp.add(i, 0);
                    return temp;
                })
                .collect(Collectors.toList());
        
        System.out.println(result);
    }
}

关于性能的补充 #

因为问题本身需要生成n+1个长度为n+1的列表，总元素数是(n+1)²，所以无论哪种实现，时间复杂度都无法低于O(n²)，上面两种方式都是该场景下的高效选择。

内容的提问来源于stack exchange，提问作者Leeren