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

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

---

链表（Linked List）

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

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

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

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

         链表的特点：

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

         如下图所示：

---

题目要求

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

输入

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

输出

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

约束

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

---

解题思路

方法一：逐一合并

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

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

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

方法三：分治合并

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

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

---

过程解析

方法一：逐一合并

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

实现步骤

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

优点

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

缺点

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

---

方法二：使用最小堆

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

实现步骤

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

优点

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

缺点

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

---

方法三：分治合并

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

实现步骤

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

优点

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

缺点

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

---

三种方法的比较

方法	时间复杂度	空间复杂度	适用场景	实现复杂度
逐一合并	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)	大规模链表合并	中等

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

---

相关知识点

1. 链表操作

   • 基本操作：插入、删除、遍历。
   • 注意指针的动态分配与释放。

2. 优先队列

   • C++ STL 中的std::priority_queue。
   • 自定义排序方式。

3. 分治策略

   • 递归与归并思想。

---

示例代码

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 为空，直接返回 l2if (!l1) return l2;// 如果 l2 为空，直接返回 l1if (!l2) return l1;// 比较两个链表头节点的值，递归合并较小值的后续节点if (l1->val < l2->val) {l1->next = mergeTwoLists(l1->next, l2); // l1 较小，递归处理 l1->nextreturn l1;                              // 返回 l1 作为新的头节点} else {l2->next = mergeTwoLists(l1, l2->next); // l2 较小，递归处理 l2->nextreturn l2;                              // 返回 l2 作为新的头节点}
}// 合并 K 个有序链表的函数
ListNode* mergeKLists(ListNode** lists, int k) {// 如果链表数组为空，直接返回 NULLif (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 -> 5ListNode* list1 = createNode(1);list1->next = createNode(4);list1->next->next = createNode(5);// 构建测试链表 2：1 -> 3 -> 4ListNode* list2 = createNode(1);list2->next = createNode(3);list2->next->next = createNode(4);// 构建测试链表 3：2 -> 6ListNode* 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;       // 初始化堆的大小为 0heap->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 -> 5ListNode* list1 = createNode(1);list1->next = createNode(4);list1->next->next = createNode(5);// 构建测试链表 2：1 -> 3 -> 4ListNode* list2 = createNode(1);list2->next = createNode(3);list2->next->next = createNode(4);// 构建测试链表 3：2 -> 6ListNode* 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

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

        10/  \15   20/ \   /30 40 25

heapify 函数的作用

void heapify(MinHeap* heap, int i);

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

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

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

实现逻辑

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

示例说明

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

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

         对应的堆结构：

        40/  \15   20/ \   /30  10 25

调用 heapify(heap, 0)

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

调整后堆数组：

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

对应堆结构：

        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

对应堆结构：

        15/  \10   20/ \   /30  40 25

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

最终堆数组：

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

 最终堆结构：

        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 为空，直接返回 l2if (!l1) return l2;// 如果 l2 为空，直接返回 l1if (!l2) return l1;// 比较两个链表的头节点，选择较小值作为合并后链表的头节点if (l1->val < l2->val) {l1->next = mergeTwoLists(l1->next, l2); // 递归处理 l1->next 和 l2return l1;                              // 返回 l1 作为当前链表头} else {l2->next = mergeTwoLists(l1, l2->next); // 递归处理 l1 和 l2->nextreturn l2;                              // 返回 l2 作为当前链表头}
}// 分治法合并 K 个有序链表
ListNode* mergeKListsDivideAndConquer(ListNode** lists, int left, int right) {// 如果左边界等于右边界，表示只剩下一个链表if (left == right) return lists[left];// 如果左边界大于右边界，返回 NULLif (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) {// 如果链表数组为空，直接返回 NULLif (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 -> 5ListNode* list1 = createNode(1);list1->next = createNode(4);list1->next->next = createNode(5);// 构建测试链表 2：1 -> 3 -> 4ListNode* list2 = createNode(1);list2->next = createNode(3);list2->next->next = createNode(4);// 构建测试链表 3：2 -> 6ListNode* list3 = createNode(2);list3->next = createNode(6);// 创建链表数组ListNode* lists[] = {list1, list2, list3};// 调用分治法合并链表ListNode* mergedList = mergeKLists(lists, 3);// 打印结果链表printf("Merged List: ");printList(mergedList);return 0; // 程序正常结束
}