multiple ordered single-linked lists fusion

针对n个长度为m的有序单链表进行合并操作，确保合并后的结果仍保持有序状态，求解该过程的时间复杂度。这道题是今年阿里巴巴武汉实习生招聘中的一道填空题，我曾参与并成功获得录取通知，但由于已提前与腾讯签约，出于诚信原则，最终选择了放弃阿里提供的较高实习薪资。我认为这是一道具有开放性的题目，因为总共有nm个元素，因此该问题的时间复杂度下限应为O(nm)。以下将分享我的思考过程（以从小到大的顺序排列）。

1.暴力法

在面对此问题时，最直接的想法是每次从所有链表中选取当前最小的元素。由于每个链表本身是有序的，因此最小元素只能出现在各链表的第一个节点中。每次选择最小值所需的时间复杂度为O(n)，而整个过程中需要执行nm次选择操作，因此整体时间复杂度达到O(nm²)，而空间复杂度则维持在O(1)。

2.最小堆

若希望更高效地找到当前所有链表中的最小元素，则可以尝试构建一个包含n个元素的最小堆结构。每次从堆顶取出当前最小值后，将其所在链表中的下一个元素补充进堆中，并重新调整堆以保持其性质。这一过程的时间复杂度为O(log(n))。由于总共需要处理nm次操作，因此整体时间复杂度为O(nm*log(n))。与此同时，在实现过程中需记录每个堆节点所对应的链表结构信息，因此需要额外的空间支持，空间复杂度为O(n)。相关代码较为简单，在此不再展示。

3.归并排序