What is the best approach to merge k sorted linked lists efficiently?

Using a min-heap ensures O(N log k) time and handles pointer updates safely. Divide and conquer merging is another optimal approach.

How do I handle empty linked lists in Merge k Sorted Lists?

Skip empty lists when inserting into the heap or during pairwise merges, ensuring you don't dereference null pointers.

Is recursive divide-and-conquer safer than iterative merging?

It reduces total merge operations and keeps pointers manageable, but you must watch recursion stack limits for large k.

Can I merge arrays using the same strategy?

Yes, heap and divide-and-conquer logic applies to arrays with similar complexity, but pointer handling translates to index management.

Why do duplicate values in lists affect pointer manipulation?

Duplicates require careful next-pointer updates to maintain list integrity; forgetting them can skip nodes or create cycles.

#23

Hard

auto_awesome链表指针操作

LeetCode 题解工作台

合并 K 个升序链表

给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。示例 1：输入： lists = [[1,4,5],[1,3,4],[2,6]] 输出： [1,1,2,3,4,4,5,6] 解释：链表数组如下： [ 1->4->5, 1->3->4, 2->…

链表分治堆（优先队列）归并排序

题目描述

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

示例 2：

输入：lists = []
输出：[]

示例 3：

输入：lists = [[]]
输出：[]

提示：

k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] 按升序排列
lists[i].length 的总和不超过 10^4

lightbulb

解题思路

方法一：优先队列（小根堆）

我们可以创建一个小根堆来 $pq$ 维护所有链表的头节点，每次从小根堆中取出值最小的节点，添加到结果链表的末尾，然后将该节点的下一个节点加入堆中，重复上述步骤直到堆为空。

时间复杂度 $O(n \times \log k)$ ，空间复杂度 $O(k)$ 。其中 $n$ 是所有链表节点数目的总和，而 $k$ 是题目给定的链表数目。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        setattr(ListNode, "__lt__", lambda a, b: a.val < b.val)
        pq = [head for head in lists if head]
        heapify(pq)
        dummy = cur = ListNode()
        while pq:
            node = heappop(pq)
            if node.next:
                heappush(pq, node.next)
            cur.next = node
            cur = cur.next
        return dummy.next

speed

复杂度分析

指标	值
时间	complexity depends on the approach: min-heap gives O(N log k), divide and conquer also O(N log k), and iterative pairwise merges can approach O(kN) in worst cases. Space complexity varies: heap requires O(k) extra space, recursive divide and conquer uses O(log k) call stack, and iterative merges can be O(1) if done in place.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Check if you are correctly maintaining all pointers during merges.
question_mark
Consider edge cases like empty lists or lists with duplicate values.
question_mark
Clarify which merging strategy optimizes both runtime and memory usage.

warning

常见陷阱

外企场景

error
Losing references to remaining nodes when reassigning pointers.
error
Not handling empty linked lists, causing null pointer errors.
error
Assuming all lists have equal lengths, leading to logic errors in merges.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Merge k sorted arrays instead of linked lists using the same heap or divide-and-conquer logic.
arrow_right_alt
Merge k nearly-sorted lists where each list has only a small number of out-of-order nodes.
arrow_right_alt
Merge k descending sorted linked lists into ascending order by reversing first or using a max-heap.

help

常见问题

外企场景

继续练习

#148 排序链表 #912 排序数组 #109 有序链表转换二叉搜索树