详解力扣第23题:合并K个升序链表
题目描述
给你一个链表数组,每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中,返回合并后的链表。
本题可以通过优先队列-最小堆来高效解决,因为我们需要频繁地找到当前K个链表中值最小的元素,并进行合并。
最小堆思路
最小堆是一种完全二叉树结构,可以在O(logK) 的时间复杂度内完成插入和删除操作,适用于需要频繁寻找最小值的场景。对于本题,使用最小堆可以有效减少每次查找最小节点的时间,从而加速链表合并的过程。
代码详解
1. 数据结构定义
我们使用链表节点(ListNode
)结构来表示输入的链表。MinHeap
结构用于实现最小堆。
#include <stdio.h>
#include <stdlib.h>
// 定义链表结构体
struct ListNode {
int val;
struct ListNode *next;
};
// 定义最小堆的结构体
struct MinHeap {
struct ListNode **array;
int size;
};
ListNode
:链表节点,val
存储节点值,next
指向下一个节点。MinHeap
:最小堆,array
存储指向链表节点的指针数组,size
表示堆中节点的数量。
2. 创建最小堆
// 创建一个新的最小堆节点
struct MinHeap* createMinHeap(int k) {
struct MinHeap* heap = (struct MinHeap*)malloc(sizeof(struct MinHeap));
heap->array = (struct ListNode**)malloc(k * sizeof(struct ListNode*));
heap->size = 0;
return heap;
}
3. 堆操作
上浮操作
// 将堆元素进行上浮
void heapifyUp(struct MinHeap* heap, int idx) {
while (idx > 0 && heap->array[(idx - 1) / 2]->val > heap->array[idx]->val) {
struct ListNode* temp = heap->array[idx];
heap->array[idx] = heap->array[(idx - 1) / 2];
heap->array[(idx - 1) / 2] = temp;
idx = (idx - 1) / 2;
}
}
上浮操作用于插入元素时保持最小堆的性质,将新元素与父节点比较,并逐步上移至合适的位置。
下沉操作
// 将堆元素进行下沉
void heapifyDown(struct MinHeap* heap, int idx) {
int smallest = idx;
int left = 2 * idx + 1;
int right = 2 * idx + 2;
if (left < heap->size && heap->array[left]->val < heap->array[smallest]->val) {
smallest = left;
}
if (right < heap->size && heap->array[right]->val < heap->array[smallest]->val) {
smallest = right;
}
if (smallest != idx) {
struct ListNode* temp = heap->array[idx];
heap->array[idx] = heap->array[smallest];
heap->array[smallest] = temp;
heapifyDown(heap, smallest);
}
}
下沉操作用于删除最小元素后保持堆的性质,将最后一个元素移动到根节点后,通过下沉操作恢复最小堆。
插入与删除最小元素
// 向堆中插入新元素
void insertMinHeap(struct MinHeap* heap, struct ListNode* node) {
heap->array[heap->size] = node;
heapifyUp(heap, heap->size);
heap->size++;
}
// 从堆中取出最小元素
struct ListNode* extractMin(struct MinHeap* heap) {
struct ListNode* root = heap->array[0];
heap->array[0] = heap->array[heap->size - 1];
heap->size--;
heapifyDown(heap, 0);
return root;
}
4. 合并K个链表
// 合并K个升序链表
struct ListNode* mergeKLists(struct ListNode** lists, int k) {
struct MinHeap* heap = createMinHeap(k);
for (int i = 0; i < k; i++) {
if (lists[i] != NULL) {
insertMinHeap(heap, lists[i]);
}
}
struct ListNode dummy;
struct ListNode* tail = &dummy;
dummy.next = NULL;
while (heap->size > 0) {
struct ListNode* minNode = extractMin(heap);
tail->next = minNode;
tail = tail->next;
if (minNode->next != NULL) {
insertMinHeap(heap, minNode->next);
}
}
return dummy.next;
}
在这里,我们将每个链表的第一个节点插入最小堆中,每次取出堆中的最小节点,将其插入到最终合并后的链表中,并将该节点的下一个节点继续插入堆中。
5. 测试代码
// 创建新节点
struct ListNode* createNode(int val) {
struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
newNode->val = val;
newNode->next = NULL;
return newNode;
}
// 打印链表
void printList(struct ListNode* head) {
while (head != NULL) {
printf("%d ", head->val);
head = head->next;
}
printf("\n");
}
// 主函数
int main() {
// 创建测试用例:[[1,4,5],[1,3,4],[2,6]]
struct ListNode* list1 = createNode(1);
list1->next = createNode(4);
list1->next->next = createNode(5);
struct ListNode* list2 = createNode(1);
list2->next = createNode(3);
list2->next->next = createNode(4);
struct ListNode* list3 = createNode(2);
list3->next = createNode(6);
struct ListNode* lists[] = {list1, list2, list3};
// 合并链表
struct ListNode* result = mergeKLists(lists, 3);
// 打印结果
printf("合并后的链表: ");
printList(result);
return 0;
}
输出结果:
合并后的链表: 1 1 2 3 4 4 5 6
最小堆插入与删除操作图解
1. 初始状态
假设我们有三个链表,每个链表的第一个元素分别是 1
、1
、2
,插入最小堆的初始状态如下:
1
/ \
1 2
2. 删除最小元素
当我们删除堆顶最小元素(值为1
)时,将 2
替换到根节点,进行下沉操作:
1
/ \
2
继续从对应链表插入下一个节点,重复此过程直到所有链表都被合并。
通过最小堆实现,合并 K 个升序链表的时间复杂度为 O(NlogK)
,其中 N 是所有链表的节点总数,K 是链表的个数。