在java中展平列表

Question

我在接受采访时被问到这个问题

给定java中的假设列表,以及保持整数内容,也可以包含另一个相似类型的列表

例: [1,3,5,[6,7],8,9,10,[11,13,15,[16,17,[18,19]]],20]

输出应该是:

[1,3,5,6,7,8,9,10,11,13,15,16,17,18,19,20]

我想的很容易!所以我带来了解决问题的递归解决方案!或不？

采访者说子列表可能会下降到任何深度,因此可能导致堆栈溢出错误!

我尝试提出非递归解决方案,但不能.谁能说出非递归解决方案可能是什么？

Answer 1

您可以将LinkedList用作堆栈.

public static List<Object> flattenNonRecursive(List<Object> list) {
    List<Object> result = new ArrayList<>();
    LinkedList<Object> stack = new LinkedList<>(list);
    while (!stack.isEmpty()) {
        Object e = stack.pop();
        if (e instanceof List<?>)
            stack.addAll(0, (List<?>)e);
        else
            result.add(e);
    }
    return result;
}

public static List<Object> list(Object... args) {
    return Arrays.asList(args);
}

public static void main(String[] args) {
    List<Object> list = list(1, 3, 5, list(6, 7), 8, 9, 10, list(11, 13, 15, list(16, 17, list(18, 19))), 20);
    System.out.println("flatten=" + flattenNonRecursive(list));
}

结果

flatten=[1, 3, 5, 6, 7, 8, 9, 10, 11, 13, 15, 16, 17, 18, 19, 20]