力扣第23题：合并K个升序链表

详解力扣第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;
}