C/C++每日一练：合并K个有序链表

本篇博客将探讨如何 “合并K个有序链表” 这一经典问题。本文将从题目要求、解题思路、过程解析和相关知识点逐步展开，同时提供详细注释的代码示例。

链表（Linked List）

链表是一种线性数据结构，由一系列节点（Node）通过指针链接在一起。与数组不同，链表中的元素在内存中不需要连续存储，每个节点包含两部分：

数据部分：存储节点的值或数据。
指针部分：存储指向下一个节点的地址（单链表）或上一个和下一个节点的地址（双向链表）。

链表的类型主要有以下几种：

单链表：每个节点只指向下一个节点。
双向链表：每个节点既有指向下一个节点的指针，也有指向上一个节点的指针。
循环链表：链表的最后一个节点指向链表的头节点，形成循环。

链表的特点：

动态大小：可以根据需要动态地增加或减少元素，无需预分配存储空间。
插入/删除效率高：在链表的任意位置进行插入或删除操作只需修改指针，不涉及大量元素的移动，效率较高。
随机访问效率低：由于链表不支持直接访问任意位置的元素，需要通过遍历来查找特定位置的节点。

如下图所示：

题目要求

给定 k 个有序的链表，要求将它们合并成一个有序链表，并返回最终的结果链表。

输入

一个包含 k 个链表的数组，其中每个链表均已按升序排列。

输出

一个合并后的链表，且链表内元素按升序排列。

约束

k >= 1
每个链表的长度可能不同，且长度总和不超过 10^5。
链表节点的值范围在 [-10^4, 10^4]。

解题思路

方法一：逐一合并

将所有链表两两合并。
时间复杂度为 O(k⋅n)，其中 n 为平均每个链表的长度。

方法二：使用最小堆（优先队列）

利用最小堆维护每个链表当前节点的最小值，逐步提取并加入结果链表。
时间复杂度为 O(n⋅log⁡k)。

方法三：分治合并

将 k 个链表两两分组合并。
类似归并排序，时间复杂度为 O(n⋅log⁡k)。

以下主要以 方法二：使用最小堆 和 方法三：分治合并 为例进行解析。

过程解析

方法一：逐一合并

思路
将第一个链表作为初始结果链表，然后逐个将剩余的链表与当前结果链表进行合并，直到所有链表合并完毕。

实现步骤

初始化结果链表为第一个链表。
遍历链表数组，调用合并两个链表的函数，将当前链表与结果链表合并。
返回最终结果链表。

优点

实现简单，逻辑清晰，适合入门时使用。

缺点

效率较低，尤其在链表数量较多或链表长度较大时。

方法二：使用最小堆

思路
利用最小堆（优先队列）维护链表当前节点的最小值，每次从堆中提取最小值并将其加入结果链表，同时推进对应链表的指针。

实现步骤

创建一个最小堆，将所有链表的头节点加入堆中。
反复提取堆顶最小值，将其加入结果链表。
如果提取的节点有下一个节点，将下一个节点加入堆中。
堆为空时，所有节点已处理完，返回结果链表。

优点

在链表数量较多时表现优秀。
保证结果链表的构建是高效的。

缺点

实现稍复杂，需要熟悉堆的数据结构。

方法三：分治合并

思路
通过分治思想，将链表分成两组，递归地合并每组链表，直到最终只剩一个合并后的链表。

实现步骤

将链表数组两两分组，递归合并每组链表。
每次合并两个链表使用合并两个有序链表的逻辑。
最终返回唯一的合并链表。

优点

效率高，适合大规模链表数量。
思路清晰，类似归并排序的合并逻辑。

缺点

实现需要递归，可能在栈深度受限的系统中受到限制。

三种方法的比较

方法	时间复杂度	空间复杂度	适用场景	实现复杂度
逐一合并	O(k⋅n)O(k \cdot n)O(k⋅n)	O(n)O(n)O(n)	链表数量较少时	简单
使用最小堆	O(n⋅log⁡k)O(n \cdot \log k)O(n⋅logk)	O(k)O(k)O(k)	链表数量较多时	中等
分治合并	O(n⋅log⁡k)O(n \cdot \log k)O(n⋅logk)	O(log⁡k)O(\log k)O(logk)	大规模链表合并	中等

如果链表数量很少，逐一合并的实现最简单，适合初学者练习。
如果链表数量较多且长度较短，最小堆法表现较优。
如果链表数量和长度都较多，分治合并法综合性能最好。

示例代码

C代码实现：逐一合并

#include <stdio.h>  // 包含标准输入输出头文件，提供 printf、scanf 等函数
#include <stdlib.h> // 包含动态内存分配和其他实用功能函数，如 malloc 和 free

// 定义链表节点结构
typedef struct ListNode {
    int val;               // 节点的值
    struct ListNode* next; // 指向下一个节点的指针
} ListNode;

// 合并两个有序链表的函数
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    // 如果 l1 为空，直接返回 l2
    if (!l1) return l2;
    // 如果 l2 为空，直接返回 l1
    if (!l2) return l1;

    // 比较两个链表头节点的值，递归合并较小值的后续节点
    if (l1->val < l2->val) {
        l1->next = mergeTwoLists(l1->next, l2); // l1 较小，递归处理 l1->next
        return l1;                              // 返回 l1 作为新的头节点
    } else {
        l2->next = mergeTwoLists(l1, l2->next); // l2 较小，递归处理 l2->next
        return l2;                              // 返回 l2 作为新的头节点
    }
}

// 合并 K 个有序链表的函数
ListNode* mergeKLists(ListNode** lists, int k) {
    // 如果链表数组为空，直接返回 NULL
    if (k == 0) return NULL;
    // 初始化结果链表为第一个链表
    ListNode* mergedList = lists[0];

    // 遍历链表数组，从第二个链表开始逐一合并
    for (int i = 1; i < k; ++i) {
        mergedList = mergeTwoLists(mergedList, lists[i]); // 合并当前结果链表和下一个链表
    }

    // 返回最终合并完成的结果链表
    return mergedList;
}

// 辅助函数：打印链表
void printList(ListNode* head) {
    // 遍历链表，打印每个节点的值
    while (head) {
        printf("%d -> ", head->val); // 输出当前节点的值
        head = head->next;          // 移动到下一个节点
    }
    printf("NULL\n"); // 链表结束后打印 NULL
}

// 辅助函数：创建链表节点
ListNode* createNode(int val) {
    // 动态分配内存为新节点
    ListNode* node = (ListNode*)malloc(sizeof(ListNode));
    node->val = val;   // 设置节点值
    node->next = NULL; // 初始化下一个节点指针为空
    return node;       // 返回新节点的指针
}

// 主函数测试
int main() 
{
    // 构建测试链表 1：1 -> 4 -> 5
    ListNode* list1 = createNode(1);
    list1->next = createNode(4);
    list1->next->next = createNode(5);

    // 构建测试链表 2：1 -> 3 -> 4
    ListNode* list2 = createNode(1);
    list2->next = createNode(3);
    list2->next->next = createNode(4);

    // 构建测试链表 3：2 -> 6
    ListNode* list3 = createNode(2);
    list3->next = createNode(6);

    // 创建链表数组存储所有链表
    ListNode* lists[] = {list1, list2, list3};

    // 合并链表
    ListNode* mergedList = mergeKLists(lists, 3);

    // 输出结果链表
    printf("Merged List: ");
    printList(mergedList);

    return 0; // 程序正常结束
}

C代码实现：最小堆解法

示例代码

#include <stdio.h>  // 包含标准输入输出头文件
#include <stdlib.h> // 包含动态内存分配函数

// 定义链表节点结构
typedef struct ListNode {
    int val;               // 节点值
    struct ListNode* next; // 指向下一个节点的指针
} ListNode;

// 定义小顶堆结构
typedef struct MinHeap {
    ListNode** array; // 存储链表节点的指针数组
    int size;         // 当前堆的大小
    int capacity;     // 堆的容量
} MinHeap;

// 创建小顶堆
MinHeap* createMinHeap(int capacity) {
    // 分配堆结构和数组的内存
    MinHeap* heap = (MinHeap*)malloc(sizeof(MinHeap));
    heap->array = (ListNode**)malloc(sizeof(ListNode*) * capacity);
    heap->size = 0;       // 初始化堆的大小为 0
    heap->capacity = capacity; // 设置堆容量
    return heap;          // 返回堆的指针
}

// 交换两个链表节点的指针
void swap(ListNode** a, ListNode** b) {
    ListNode* temp = *a;
    *a = *b;
    *b = temp;
}

// 堆化调整函数（维护堆的性质）
void heapify(MinHeap* heap, int i) {
    int smallest = i;            // 假设当前节点为最小值
    int left = 2 * i + 1;        // 左子节点索引
    int right = 2 * i + 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 != i) {
        swap(&heap->array[i], &heap->array[smallest]);
        heapify(heap, smallest);
    }
}

// 将节点插入到堆中
void insertHeap(MinHeap* heap, ListNode* node) {
    // 将新节点放在堆末尾
    heap->array[heap->size++] = node;
    int i = heap->size - 1; // 当前节点的索引

    // 向上调整节点位置以维护堆的性质
    while (i && heap->array[(i - 1) / 2]->val > heap->array[i]->val) {
        swap(&heap->array[i], &heap->array[(i - 1) / 2]);
        i = (i - 1) / 2; // 移动到父节点
    }
}

// 从堆中提取最小值节点
ListNode* extractMin(MinHeap* heap) {
    if (heap->size == 0) return NULL; // 堆为空时返回 NULL

    // 获取堆顶最小值
    ListNode* root = heap->array[0];
    // 将堆末尾的节点移到堆顶
    heap->array[0] = heap->array[--heap->size];
    // 调整堆以恢复堆的性质
    heapify(heap, 0);
    return root; // 返回提取的最小值节点
}

// 合并 K 个有序链表的函数
ListNode* mergeKLists(ListNode** lists, int k) {
    // 创建最小堆
    MinHeap* heap = createMinHeap(k);

    // 将每个链表的头节点加入堆中
    for (int i = 0; i < k; ++i) {
        if (lists[i]) insertHeap(heap, lists[i]);
    }

    // 创建结果链表的哑节点（dummy 节点）
    ListNode dummy;
    ListNode* tail = &dummy; // 结果链表的尾部指针
    dummy.next = NULL;

    // 从堆中逐一提取最小值节点并加入结果链表
    while (heap->size > 0) {
        // 提取堆中的最小值节点
        ListNode* minNode = extractMin(heap);
        // 将最小值节点连接到结果链表
        tail->next = minNode;
        tail = tail->next; // 更新尾部指针

        // 如果提取的节点还有下一个节点，将其加入堆中
        if (minNode->next) insertHeap(heap, minNode->next);
    }

    // 释放堆的内存
    free(heap->array);
    free(heap);
    return dummy.next; // 返回结果链表的头节点
}

// 辅助函数：打印链表
void printList(ListNode* head) {
    while (head) {
        printf("%d -> ", head->val); // 打印节点值
        head = head->next;          // 移动到下一个节点
    }
    printf("NULL\n"); // 链表结束
}

// 辅助函数：创建链表节点
ListNode* createNode(int val) {
    ListNode* node = (ListNode*)malloc(sizeof(ListNode)); // 分配内存
    node->val = val;   // 设置节点值
    node->next = NULL; // 初始化下一个指针
    return node;
}

// 主函数测试
int main() 
{
    // 构建测试链表 1：1 -> 4 -> 5
    ListNode* list1 = createNode(1);
    list1->next = createNode(4);
    list1->next->next = createNode(5);

    // 构建测试链表 2：1 -> 3 -> 4
    ListNode* list2 = createNode(1);
    list2->next = createNode(3);
    list2->next->next = createNode(4);

    // 构建测试链表 3：2 -> 6
    ListNode* list3 = createNode(2);
    list3->next = createNode(6);

    // 创建链表数组
    ListNode* lists[] = {list1, list2, list3};

    // 合并链表
    ListNode* mergedList = mergeKLists(lists, 3);

    // 输出结果链表
    printf("Merged List: ");
    printList(mergedList);

    return 0; // 程序结束
}

补充

小顶堆性质

小顶堆（Min-Heap）是一种完全二叉树，它具有以下性质：

堆的结构性质：

小顶堆是一棵完全二叉树，即树是从左到右逐层填满的，只有最后一层可能不满，但节点必须从左向右连续排列。

堆的值性质：

每个节点的值都小于或等于其子节点的值。
即：对于任意节点 i，有：

A[i] ≤ A[2i+1](左子节点值)
A[i] ≤ A[2i+2](右子节点值)

由于这两个性质，堆的最小值始终存储在根节点（即数组的第一个位置）。

数组表示：堆可以使用数组表示，将完全二叉树的节点按层序遍历的顺序存储：

索引:     0   1   2   3   4   5
值:       10  15  20  30  40  25

在数组中，可以通过以下规则找到父子节点的关系：

父节点索引： parent(i) = (i−1) / 2
左子节点索引： left(i) = 2i+1
右子节点索引： right(i) = 2i+2

示例：一个满足小顶堆性质的完全二叉树：

heapify 函数的作用

void heapify(MinHeap* heap, int i);

i: 要调整的节点在堆数组中的索引。
heap: 表示一个小顶堆，包含节点数组和堆的大小。

heapify 函数是小顶堆的调整函数，用来维护堆的性质（即每个节点的值都不大于其子节点的值）。它的作用是：

从索引 i 开始，将子树调整为满足小顶堆性质。
如果某节点不满足小顶堆性质，则通过交换该节点和其较小子节点的值，并递归调整子树，直到整个堆满足小顶堆性质。

实现逻辑

假设当前节点的值是最小的（设索引为 smallest）。
比较当前节点和其左、右子节点的值：
- 如果左子节点更小，更新 smallest为左子节点索引。
- 如果右子节点更小，更新 smallest为右子节点索引。
如果 smallest 发生变化（当前节点不是最小值），交换当前节点和 smallest的值。
递归调用 heapify，确保调整后的子树也满足小顶堆性质。

示例说明

假设有以下堆数组，表示一个不完全满足小顶堆性质的堆：

索引:      0   1   2   3   4   5
值:        40  15  20  30  10  25

对应的堆结构：

调用 heapify(heap, 0)

当前节点： 40（索引 0）。
左子节点：15（索引 1）。
右子节点：20（索引 2）。
最小值为左子节点 15，交换 40 和 15。

调整后堆数组：

索引:      0   1   2   3   4   5
值:        15  40  20  30  10  25

对应堆结构：

递归调用 heapify(heap, 1)：

当前节点：40（索引 1）。
左子节点：30（索引 3）。
右子节点：10（索引 4）。
最小值为右子节点 10，交换 40 和 10。

调整后堆数组：

索引:      0   1   2   3   4   5
值:        15  10  20  30  40  25

对应堆结构：

heapify(heap, 4) 不再需要调整，因为 40 没有子节点。

最终堆数组：

索引:      0   1   2   3   4   5
值:        15  10  20  30  40  25

最终堆结构：

C++代码实现：分治解法

#include <stdio.h>  // 包含标准输入输出头文件
#include <stdlib.h> // 包含动态内存分配函数

// 定义链表节点结构
typedef struct ListNode {
    int val;               // 节点值
    struct ListNode* next; // 指向下一个节点的指针
} ListNode;

// 合并两个有序链表的函数
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    // 如果 l1 为空，直接返回 l2
    if (!l1) return l2;
    // 如果 l2 为空，直接返回 l1
    if (!l2) return l1;

    // 比较两个链表的头节点，选择较小值作为合并后链表的头节点
    if (l1->val < l2->val) {
        l1->next = mergeTwoLists(l1->next, l2); // 递归处理 l1->next 和 l2
        return l1;                              // 返回 l1 作为当前链表头
    } else {
        l2->next = mergeTwoLists(l1, l2->next); // 递归处理 l1 和 l2->next
        return l2;                              // 返回 l2 作为当前链表头
    }
}

// 分治法合并 K 个有序链表
ListNode* mergeKListsDivideAndConquer(ListNode** lists, int left, int right) {
    // 如果左边界等于右边界，表示只剩下一个链表
    if (left == right) return lists[left];
    // 如果左边界大于右边界，返回 NULL
    if (left > right) return NULL;

    // 计算中间位置
    int mid = left + (right - left) / 2;

    // 递归地合并左半部分链表
    ListNode* l1 = mergeKListsDivideAndConquer(lists, left, mid);
    // 递归地合并右半部分链表
    ListNode* l2 = mergeKListsDivideAndConquer(lists, mid + 1, right);

    // 合并左右两部分链表
    return mergeTwoLists(l1, l2);
}

// 主函数入口，用于调用分治法合并链表
ListNode* mergeKLists(ListNode** lists, int k) {
    // 如果链表数组为空，直接返回 NULL
    if (k == 0) return NULL;
    // 调用分治法进行合并
    return mergeKListsDivideAndConquer(lists, 0, k - 1);
}

// 辅助函数：打印链表
void printList(ListNode* head) {
    while (head) {
        printf("%d -> ", head->val); // 打印当前节点的值
        head = head->next;          // 移动到下一个节点
    }
    printf("NULL\n"); // 链表结束
}

// 辅助函数：创建链表节点
ListNode* createNode(int val) {
    ListNode* node = (ListNode*)malloc(sizeof(ListNode)); // 分配内存
    node->val = val;   // 设置节点值
    node->next = NULL; // 初始化指针
    return node;       // 返回新节点
}

// 主函数测试
int main() 
{
    // 构建测试链表 1：1 -> 4 -> 5
    ListNode* list1 = createNode(1);
    list1->next = createNode(4);
    list1->next->next = createNode(5);

    // 构建测试链表 2：1 -> 3 -> 4
    ListNode* list2 = createNode(1);
    list2->next = createNode(3);
    list2->next->next = createNode(4);

    // 构建测试链表 3：2 -> 6
    ListNode* list3 = createNode(2);
    list3->next = createNode(6);

    // 创建链表数组
    ListNode* lists[] = {list1, list2, list3};

    // 调用分治法合并链表
    ListNode* mergedList = mergeKLists(lists, 3);

    // 打印结果链表
    printf("Merged List: ");
    printList(mergedList);

    return 0; // 程序正常结束
}