具有递归循环问题的LinkedList of LinkedList

Question

我有一个列表结构列表和一个名为树的递归函数。在下面的代码中，它永远不会到达current == null语句，因此它将永远运行。

如果我不能使用null，解决方案是什么？

private void tree(LinkedList<LinkedList<String>> partitions, LinkedList<String> part)
{
    LinkedList<String> current = findBiggerPartitionContained(partitions, part);
    if (current == null) {
        return;
    }
    tree(partitions, current);
}

private LinkedList<String> findBiggerPartitionContained(LinkedList<LinkedList<String>> partitions, LinkedList<String> part)
{
    LinkedList<String> max = new LinkedList<>();

    boolean flag = false;
    for (LinkedList<String> item : partitions) {
        if (item.size() > max.size() && part.containsAll(max)) {
            max = item;
            flag = true;
        }
    }

    if (!flag)
        return null;
    flag = false;
    return max;
}

Answer 1

大多数情况下，flag将是true，因为条件测试item.size() > max.size()，而max是用空列表初始化的。当max为空时，表达式part.containsAll(max)也将是true，这将导致意外的结果。

为了解决这个问题，您可以在findBiggerPartitionContained中使用它

if (item.size() > max.size() && item.containsAll(part)) {
    max = item;
    flag = true;
}

在tree中

if (current.equals(part)) {
    return;
} else {
    tree(partitions, current);
}

如果我的理解是正确的，那么您将在partitions中寻找包含part的最大列表。也许以下内容不太容易出错，而且更容易读懂：

List<String> result = partitions.stream().filter(list -> list.containsAll(part))
                                         .max(Comparator.comparingInt(List::size))
                                         .orElse(null);

您可以用这个MCVE测试它。

List<String> p0 = new LinkedList<>(Arrays.asList("a", "b", "c"));
List<String> p1 = new LinkedList<>(Arrays.asList("a", "b"));
List<String> p2 = new LinkedList<>(Arrays.asList("a", "b", "c", "d"));
List<String> p3 = new LinkedList<>(Arrays.asList("a", "b", "e", "d"));
List<List<String>> partitions = Arrays.asList(p0, p1, p2, p3);

List<String> part = new LinkedList<>(Arrays.asList("a", "b", "e"));

List<String> result = partitions.stream().filter(list -> list.containsAll(part))
                                         .max(Comparator.comparingInt(List::size))
                                         .orElse(null);

System.out.println(result);

请记住，这可能返回null来处理缺席的Optional。