常平网站,做网站要会写什么软件,滨州网站定制,网站制作建设建议兴田德润本篇博客将探讨如何 “合并K个有序链表” 这一经典问题。本文将从题目要求、解题思路、过程解析和相关知识点逐步展开#xff0c;同时提供详细注释的代码示例。 链表#xff08;Linked List#xff09; 链表是一种线性数据结构#xff0c;由一系列节点#xff08;Node同时提供详细注释的代码示例。 链表Linked List 链表是一种线性数据结构由一系列节点Node通过指针链接在一起。与数组不同链表中的元素在内存中不需要连续存储每个节点包含两部分
数据部分存储节点的值或数据。指针部分存储指向下一个节点的地址单链表或上一个和下一个节点的地址双向链表。 链表的类型主要有以下几种
单链表每个节点只指向下一个节点。双向链表每个节点既有指向下一个节点的指针也有指向上一个节点的指针。循环链表链表的最后一个节点指向链表的头节点形成循环。 链表的特点
动态大小可以根据需要动态地增加或减少元素无需预分配存储空间。插入/删除效率高在链表的任意位置进行插入或删除操作只需修改指针不涉及大量元素的移动效率较高。随机访问效率低由于链表不支持直接访问任意位置的元素需要通过遍历来查找特定位置的节点。 如下图所示 题目要求 给定 k 个有序的链表要求将它们合并成一个有序链表并返回最终的结果链表。
输入
一个包含 k 个链表的数组其中每个链表均已按升序排列。
输出
一个合并后的链表且链表内元素按升序排列。
约束
k 1每个链表的长度可能不同且长度总和不超过 10^5。链表节点的值范围在 [-10^4, 10^4]。 解题思路
方法一逐一合并
将所有链表两两合并。时间复杂度为 O(k⋅n)其中 n 为平均每个链表的长度。
方法二使用最小堆优先队列
利用最小堆维护每个链表当前节点的最小值逐步提取并加入结果链表。时间复杂度为 O(n⋅logk)。
方法三分治合并
将 k 个链表两两分组合并。类似归并排序时间复杂度为 O(n⋅logk)。
以下主要以 方法二使用最小堆 和 方法三分治合并 为例进行解析。 过程解析
方法一逐一合并
思路 将第一个链表作为初始结果链表然后逐个将剩余的链表与当前结果链表进行合并直到所有链表合并完毕。
实现步骤
初始化结果链表为第一个链表。遍历链表数组调用合并两个链表的函数将当前链表与结果链表合并。返回最终结果链表。
优点
实现简单逻辑清晰适合入门时使用。
缺点
效率较低尤其在链表数量较多或链表长度较大时。 方法二使用最小堆
思路 利用最小堆优先队列维护链表当前节点的最小值每次从堆中提取最小值并将其加入结果链表同时推进对应链表的指针。
实现步骤
创建一个最小堆将所有链表的头节点加入堆中。反复提取堆顶最小值将其加入结果链表。如果提取的节点有下一个节点将下一个节点加入堆中。堆为空时所有节点已处理完返回结果链表。
优点
在链表数量较多时表现优秀。保证结果链表的构建是高效的。
缺点
实现稍复杂需要熟悉堆的数据结构。 方法三分治合并
思路 通过分治思想将链表分成两组递归地合并每组链表直到最终只剩一个合并后的链表。
实现步骤
将链表数组两两分组递归合并每组链表。每次合并两个链表使用合并两个有序链表的逻辑。最终返回唯一的合并链表。
优点
效率高适合大规模链表数量。思路清晰类似归并排序的合并逻辑。
缺点
实现需要递归可能在栈深度受限的系统中受到限制。 三种方法的比较
方法时间复杂度空间复杂度适用场景实现复杂度逐一合并O(k⋅n)O(k \cdot n)O(k⋅n)O(n)O(n)O(n)链表数量较少时简单使用最小堆O(n⋅logk)O(n \cdot \log k)O(n⋅logk)O(k)O(k)O(k)链表数量较多时中等分治合并O(n⋅logk)O(n \cdot \log k)O(n⋅logk)O(logk)O(\log k)O(logk)大规模链表合并中等
如果链表数量很少逐一合并的实现最简单适合初学者练习。如果链表数量较多且长度较短最小堆法表现较优。如果链表数量和长度都较多分治合并法综合性能最好。 相关知识点 链表操作 基本操作插入、删除、遍历。注意指针的动态分配与释放。 优先队列 C STL 中的std::priority_queue。自定义排序方式。 分治策略 递归与归并思想。 示例代码
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()
{// 构建测试链表 11 - 4 - 5ListNode* list1 createNode(1);list1-next createNode(4);list1-next-next createNode(5);// 构建测试链表 21 - 3 - 4ListNode* list2 createNode(1);list2-next createNode(3);list2-next-next createNode(4);// 构建测试链表 32 - 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()
{// 构建测试链表 11 - 4 - 5ListNode* list1 createNode(1);list1-next createNode(4);list1-next-next createNode(5);// 构建测试链表 21 - 3 - 4ListNode* list2 createNode(1);list2-next createNode(3);list2-next-next createNode(4);// 构建测试链表 32 - 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[2i1](左子节点值)
A[i] ≤ A[2i2](右子节点值) 由于这两个性质堆的最小值始终存储在根节点即数组的第一个位置。 数组表示堆可以使用数组表示将完全二叉树的节点按层序遍历的顺序存储
索引: 0 1 2 3 4 5
值: 10 15 20 30 40 25在数组中可以通过以下规则找到父子节点的关系
父节点索引 parent(i) (i−1) / 2左子节点索引 left(i) 2i1右子节点索引 right(i) 2i2
示例一个满足小顶堆性质的完全二叉树 10/ \15 20/ \ /30 40 25heapify 函数的作用
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对应的堆结构 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对应堆结构 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 25heapify(heap, 4) 不再需要调整因为 40 没有子节点。
最终堆数组
索引: 0 1 2 3 4 5
值: 15 10 20 30 40 25最终堆结构 15/ \10 20/ \ /30 40 25C代码实现分治解法
#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()
{// 构建测试链表 11 - 4 - 5ListNode* list1 createNode(1);list1-next createNode(4);list1-next-next createNode(5);// 构建测试链表 21 - 3 - 4ListNode* list2 createNode(1);list2-next createNode(3);list2-next-next createNode(4);// 构建测试链表 32 - 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; // 程序正常结束
}
