我有一个情况，如下:
- 我有n个双向链表
- 每个列表都有一个标记开始和结束
- 所有列表都有相同的开始和结束节点(不是必需的，但为了简单起见)
- 列表是同质的并且可以共享项目
我想找到所有 n 列表中所有节点的部分排序，从开始节点开始到结束节点结束，这样出现在 n 中的任何节点em>n-x 列表，其中 x < n，将根据它出现的所有列表中的其他节点进行排序。
使用数组提供一组示例列表:
first = [a, b, d, f, h, i];
second = [a, b, c, f, g, i];
third = [a, e, f, g, h, i];
显然，一个可能的答案是 [a, b, c, d, e, f, g, h, i]，但另一种可接受的顺序是 [a, b, d, e, c, f, g , h, i].
我知道有一个快速的算法可以做到这一点，有人记得它是怎么回事或者它叫什么吗？我已经有几个慢版本，但我确信在 Knuth 的某个地方有一个快得多的版本。
(而且，在你问之前，这不是作业或欧拉计划，我不能再具体了。这是问题所在。)
编辑:我相对确定只要端点位于所有列表中且位置相同(开始和结束)，就可以定义偏序。我不反对通过线性时间搜索来找到这些端点，如果找不到它们，就会在那里引发错误。
最佳答案
看起来与 Topological sort 非常相似大部头书。有几种算法可以让您获得拓扑排序的状态。我特别喜欢的一个类似于广度优先搜索。维护两个列表，其中一个是没有边的所有节点，例如 L(最初只是 a 节点)，另一个是部分有序节点， F。现在在每一步，
pick a node from `L`,
do some operations (explained later),
and move the chosen node to the `F` list.
在“做一些操作步骤”中，
choose all successors of the source node which have exactly one in-link add them to L.
Remove the link from the source node to all the successors in the previous step
现在，列表 F 对所有节点进行了拓扑排序。对于糟糕的解释，我很抱歉，维基链接有很好的图表:)
关于快速获取多个链表偏序的算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/6390205/