如何合并含递归公共属性的列表？Scala实现方案求助

这个问题本质上是要找出集合的连通分量：把所有有直接或间接交集的列表合并成一个独立集合，完全无交集的列表则单独保留。用Scala的集合API配合foldLeft就能实现纯函数式的解决方案，不用任何可变数据结构，正好符合你的需求。

完整的merge方法实现 #

def merge(lists: List[List[Int]]): List[List[Int]] = {
  lists.foldLeft(List.empty[List[Int]]) { (acc, current) =>
    // 将已合并的列表分成与当前列表有交集的（连通的）和无交集的（不连通的）
    val (connected, disconnected) = acc.partition(group => group.intersect(current).nonEmpty)
    
    if (connected.nonEmpty) {
      // 合并所有连通的列表和当前列表，去重并排序后加入结果
      val mergedGroup = (current ++ connected.flatten).distinct.sorted
      mergedGroup :: disconnected
    } else {
      // 当前列表无交集，直接加入结果
      current :: disconnected
    }
  }
}

代码逻辑解释 #

我们用foldLeft迭代所有输入列表，维护一个累积结果acc——其中每个元素都是已经合并完成、互不相交的集合：

1. 分区操作：对每个当前列表current，把acc分成两部分：connected是和current有交集的所有已合并集合，disconnected是完全无交集的集合。
2. 合并连通集合：如果connected不为空，说明current需要和这些连通的集合合并成一个新集合——把current的元素和所有connected的元素拼接、去重、排序，得到新的合并集合，再和disconnected组合成新的acc。
3. 添加独立集合：如果connected为空，说明current是一个独立的集合，直接把它加入acc即可。

测试你的示例输入 #

把你给出的输入传入这个方法：

val input = List(List(1,2), List(3,4), List(1000), List(5,6), List(100, 1,3), List(99, 4, 5))
println(merge(input))
// 输出：List(List(1,2,3,4,5,6,99,100), List(1000))

完全符合你的期望输出。

额外说明 #

• 这个写法是纯函数式的，没有任何可变状态，所有操作都是基于集合的不可变转换。
• 代码里的sorted是为了让输出和你的期望一致，如果不需要有序，可以去掉这个调用。
• 如果处理超大规模数据，这个方法的性能可能不如并查集（Union-Find），但对于大多数常规场景，它的简洁性和可读性更有优势。

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