language-agnostic - 对有序链表的集合进行排序

Question

我正在寻找一个优雅、高性能的解决方案来解决以下问题。

有256个链表。

• 每个列表都包含相同类型的对象，其中包含一个用于定义排序顺序的整数。
• 所有列表中的所有数字都是唯一的
• 每个单独的列表都按这些数字升序排序

如何从 256 个原始链表中的所有对象创建一个升序排序列表？我不想强行使用它，并且有一些其他的想法，但这似乎是那些有标准、最佳解决方案的问题之一。

Answer 1

您可以使用一个优先级队列来保存 256 个链表中每个链表的“最顶层”项。这个“最顶层”的项目是计划插入到结果列表中的项目。这样，您可以只从优先级队列中取出最小的元素，将其插入到结果队列中，并将其下一个元素插入到优先级队列中:

# Preprocessing:
result = list.new()
queue = priority_queue.new()

foreach (list in lists):
    queue.push(list.first())

# Main loop:
while (not queue.empty()):
    node = queue.pop()
    result.insert(node)
    if (node.next() != null):
        queue.push(node.next())