算法题——合并 k 个升序的链表

题目描述：
 

合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点。

数据范围：节点总数 0≤n≤50000≤n≤5000，每个节点的val满足 ∣val∣<=1000∣val∣<=1000

要求：时间复杂度 O(nlogn)

---

一、常见解法

（一）暴力排序法

暴力排序法的思路非常直接。首先，将链表数组中的所有链表进行遍历，把它们头尾相接组成一个长链表。这个过程可以通过遍历链表数组，对于每个链表，依次将其节点添加到新的长链表中。然后，对这个长链表进行排序。这种方法虽然简单易懂，但是时间复杂度比较高。因为在组成长链表的过程中，需要遍历整个链表数组，时间复杂度为 O(k * n)，其中 是链表数组的长度， n是平均每个链表的长度。而对长链表进行排序的时间复杂度取决于排序算法的选择，例如快速排序的平均时间复杂度为 O(nlogn)，其中 n是长链表的长度，也就是所有链表长度之和。所以总体时间复杂度较高，但对于一些小规模的问题或者对时间要求不高的场景，这种方法仍然可以尝试。

（二）暴力求解优化法

暴力求解优化法是对暴力排序法的一种改进。它的核心思想是每次取出 K个链表中最小的元素，不断放入结果数组中。具体实现时，可以通过遍历 K个链表的首元素，找到其中最小的元素，将其加入结果数组，然后将该最小元素所在链表的指针向后移动一位。重复这个过程，直到所有链表都为空。这种方法在一定程度上减少了不必要的排序操作，但是时间复杂度仍然较高。每次查找最小元素需要遍历 K个链表，时间复杂度为 O(k)，假设总共有 n个元素，那么总体时间复杂度为 O(nk)。

（三）分治法

分治法是一种更加高效的方法。将 k个链表配对并将同一对中的链表合并。第一轮合并以后， k个链表被合并成了 k/2个链表，平均长度为 2n/k，然后是 k/4个链表，k/8 个链表等等。重复这一过程，直到我们得到了最终的有序链表。具体实现时，可以使用递归的方式进行合并。首先将链表数组分成两部分，分别对这两部分进行合并，然后再将合并后的结果进行合并。这种方法的时间复杂度为 O(n log k)，其中 n是所有链表的总长度，k 是链表数组的长度。因为每次合并的时间复杂度为 O(n)，而总共需要进行 log k次合并。

（四）堆排序或构建二叉排序树法

堆排序或构建二叉排序树法为解决这个问题提供了不同的思路。对于堆排序，可以使用小根堆来存储链表的首元素。每次从堆中取出最小的元素，将其加入结果链表，然后将该元素所在链表的下一个元素加入堆中。这样可以保证每次取出的元素都是当前未处理元素中的最小值。时间复杂度为 O(n log k)，其中 n是所有链表的总长度，k 是链表数组的长度。对于构建二叉排序树，可以将每个链表的元素依次插入二叉排序树中，然后进行中序遍历得到有序链表。这种方法的时间复杂度取决于二叉排序树的构建和遍历，一般情况下时间复杂度也为 O(n log k)。具体的实现可以参考相关博客中的更基础概念和示例代码。

二、代码实现

（一）暴力排序法

#include <stdio.h>
#include <stdlib.h>// 链表节点结构
struct ListNode {int val;struct ListNode* next;
};// 创建新节点
struct ListNode* createNode(int val) {// 分配内存空间给新节点struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));// 设置新节点的值newNode->val = val;// 新节点的下一个指针初始化为 NULLnewNode->next = NULL;return newNode;
}// 插入节点到链表尾部
void insertNode(struct ListNode** head, int val) {// 创建新节点struct ListNode* new = createNode(val);// 如果链表为空，将新节点设为链表的头节点if (*head == NULL) {*head = new;return;}// 临时指针指向链表的头节点struct ListNode* temp = *head;// 遍历链表找到最后一个节点while (temp->next!= NULL) {temp = temp->next;}// 将新节点连接到链表的末尾temp->next = new;
}// 合并 k 个链表（暴力排序法）
struct ListNode* mergeKListsBruteForce(struct ListNode** lists, int listsSize) {// 初始化结果链表为空struct ListNode* result = NULL;// 遍历输入的链表数组for (int i = 0; i < listsSize; i++) {// 获取当前链表struct ListNode* currentList = lists[i];// 遍历当前链表的所有节点while (currentList!= NULL) {// 将当前链表的节点值插入到结果链表中insertNode(&result, currentList->val);// 移动到当前链表的下一个节点currentList = currentList->next;}}// 对合并后的链表进行排序struct ListNode* current = result;while (current!= NULL) {// 获取当前节点的下一个节点struct ListNode* next = current->next;while (next!= NULL) {// 如果当前节点的值大于下一个节点的值，则交换它们的值if (current->val > next->val) {int temp = current->val;current->val = next->val;next->val = temp;}// 移动到下一个节点next = next->next;}// 移动到下一个节点current = current->next;}return result;
}

（二）暴力求解优化法

#include <stdio.h>
#include <stdlib.h>// 链表节点结构
struct ListNode {int val;struct ListNode* next;
};// 创建新节点
struct ListNode* createNode(int val) {// 分配内存空间给新节点struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));// 设置新节点的值newNode->val = val;// 新节点的下一个指针初始化为 NULLnewNode->next = NULL;return newNode;
}// 插入节点到链表尾部
void insertNode(struct ListNode** head, int val) {// 创建新节点struct ListNode* new = createNode(val);// 如果链表为空，将新节点设为链表的头节点if (*head == NULL) {*head = new;return;}// 临时指针指向链表的头节点struct ListNode* temp = *head;// 遍历链表找到最后一个节点while (temp->next!= NULL) {temp = temp->next;}// 将新节点连接到链表的末尾temp->next = new;
}// 查找 k 个链表中的最小节点所在的链表索引
int findMinIndex(struct ListNode** lists, int listsSize) {// 初始化最小索引为 -1，表示还未找到最小节点所在的链表int minIndex = -1;// 初始化最小值为整数最大值int minVal = __INT_MAX__;// 遍历所有链表for (int i = 0; i < listsSize; i++) {// 如果当前链表不为空且当前链表的头节点值小于当前最小值if (lists[i]!= NULL && lists[i]->val < minVal) {// 更新最小值minVal = lists[i]->val;// 更新最小索引minIndex = i;}}return minIndex;
}// 合并 k 个链表（暴力求解优化法）
struct ListNode* mergeKListsOptimized(struct ListNode** lists, int listsSize) {// 创建一个虚拟头节点struct ListNode* dummy = createNode(0);// 当前节点指针，初始指向虚拟头节点struct ListNode* current = dummy;// 记录非空链表的数量int nonEmptyLists = listsSize;// 当还有非空链表时循环while (nonEmptyLists > 0) {// 找到 k 个链表中最小节点所在的链表索引int minIndex = findMinIndex(lists, listsSize);// 如果找到了非空链表if (minIndex!= -1) {// 将最小节点连接到结果链表中current->next = lists[minIndex];// 当前节点指针后移current = current->next;// 移动最小链表的头指针到下一个节点lists[minIndex] = lists[minIndex]->next;// 如果该链表为空，减少非空链表数量if (lists[minIndex] == NULL) {nonEmptyLists--;}}}// 返回合并后的链表（不包括虚拟头节点）return dummy->next;
}

（三）分治法

#include <stdio.h>
#include <stdlib.h>// 链表节点结构
struct ListNode {int val;struct ListNode* next;
};// 创建新节点
struct ListNode* createNode(int val) {// 分配内存空间给新节点struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));// 设置新节点的值newNode->val = val;// 新节点的下一个指针初始化为 NULLnewNode->next = NULL;return newNode;
}// 插入节点到链表尾部
void insertNode(struct ListNode** head, int val) {// 创建新节点struct ListNode* new = createNode(val);// 如果链表为空，将新节点设为链表的头节点if (*head == NULL) {*head = new;return;}// 临时指针指向链表的头节点struct ListNode* temp = *head;// 遍历链表找到最后一个节点while (temp->next!= NULL) {temp = temp->next;}// 将新节点连接到链表的末尾temp->next = new;
}// 合并两个升序链表
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {// 创建一个虚拟头节点struct ListNode dummy;// 指向虚拟头节点的指针，用于构建合并后的链表struct ListNode* tail = &dummy;// 当两个链表都不为空时循环while (l1 && l2) {// 如果第一个链表当前节点值小于第二个链表当前节点值if (l1->val < l2->val) {// 将第一个链表当前节点连接到结果链表tail->next = l1;// 移动第一个链表指针到下一个节点l1 = l1->next;} else {// 将第二个链表当前节点连接到结果链表tail->next = l2;// 移动第二个链表指针到下一个节点l2 = l2->next;}// 移动结果链表指针到新连接的节点tail = tail->next;}// 将剩余的非空链表连接到结果链表末尾tail->next = l1? l1 : l2;// 返回合并后的链表（不包括虚拟头节点）return dummy.next;
}// 分治法合并 k 个链表
struct ListNode* mergeKListsDivideAndConquer(struct ListNode** lists, int start, int end) {// 如果起始索引等于结束索引，说明只有一个链表，直接返回该链表if (start == end) {return lists[start];}// 如果起始索引大于结束索引，说明没有链表可合并，返回 NULLif (start > end) {return NULL;}// 计算中间索引int mid = start + (end - start) / 2;// 递归合并左半部分链表struct ListNode* left = mergeKListsDivideAndConquer(lists, start, mid);// 递归合并右半部分链表struct ListNode* right = mergeKListsDivideAndConquer(lists, mid + 1, end);// 合并左右两部分已合并的链表return mergeTwoLists(left, right);
}

（四）堆排序或构建二叉排序树法

#include <stdio.h>
#include <stdlib.h>// 链表节点结构
struct ListNode {int val;struct ListNode* next;
};// 创建新节点
struct ListNode* createNode(int val) {// 分配内存空间给新节点struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));// 设置新节点的值newNode->val = val;// 新节点的下一个指针初始化为 NULLnewNode->next = NULL;return newNode;
}// 插入节点到链表尾部
void insertNode(struct ListNode** head, int val) {// 创建新节点struct ListNode* new = createNode(val);// 如果链表为空，将新节点设为链表的头节点if (*head == NULL) {*head = new;return;}// 临时指针指向链表的头节点struct ListNode* temp = *head;// 遍历链表找到最后一个节点while (temp->next!= NULL) {temp = temp->next;}// 将新节点连接到链表的末尾temp->next = new;
}// 交换两个整数的值
void swap(int* a, int* b) {// 临时变量存储其中一个整数的值int temp = *a;// 将另一个整数的值赋给第一个整数*a = *b;// 将临时变量的值赋给第二个整数*b = temp;
}// 堆调整函数
void heapify(int arr[], int n, int i) {// 初始化当前最大元素的索引为 iint largest = i;// 左子节点的索引int left = 2 * i + 1;// 右子节点的索引int right = 2 * i + 2;// 如果左子节点存在且比当前最大元素大if (left < n && arr[left] > arr[largest])largest = left;// 如果右子节点存在且比当前最大元素大if (right < n && arr[right] > arr[largest])largest = right;// 如果最大元素不是当前节点if (largest!= i) {// 交换当前节点和最大元素节点的值swap(&arr[i], &arr[largest]);// 递归调整新的子树heapify(arr, n, largest);}
}// 构建堆
void buildHeap(int arr[], int n) {// 从最后一个非叶子节点开始调整堆for (int i = n / 2 - 1; i >= 0; i--)heapify(arr, n, i);
}// 合并 k 个链表（堆排序法）
struct ListNode* mergeKListsHeap(struct ListNode** lists, int listsSize) {// 创建最小堆数组int minHeap[listsSize];int heapSize = 0;// 将每个链表的第一个节点的值加入最小堆数组for (int i = 0; i < listsSize; i++) {if (lists[i]!= NULL) {minHeap[heapSize++] = lists[i]->val;}}// 构建最小堆buildHeap(minHeap, heapSize);// 创建虚拟头节点struct ListNode dummy;struct ListNode* tail = &dummy;// 当堆不为空时循环while (heapSize > 0) {// 获取堆顶元素（最小元素）int minVal = minHeap[0];// 将最小元素加入结果链表tail->next = createNode(minVal);tail = tail->next;// 在链表数组中找到值为最小元素的链表，并将其头节点后移for (int i = 0; i < listsSize; i++) {if (lists[i]!= NULL && lists[i]->val == minVal) {lists[i] = lists[i]->next;if (lists[i]!= NULL) {// 如果该链表不为空，将新的头节点值加入堆minHeap[0] = lists[i]->val;} else {// 如果该链表为空，用堆的最后一个元素替换堆顶元素，并减小堆大小minHeap[0] = minHeap[--heapSize];}// 调整堆heapify(minHeap, heapSize, 0);break;}}}// 返回合并后的链表（不包括虚拟头节点）return dummy.next;
}

三、总结展望

1.暴力排序法：

• 优点：思路简单直接，容易理解和实现。对于小规模问题或者对时间要求不高的场景，可以快速解决问题。
• 缺点：时间复杂度高，特别是在处理大规模数据或者链表数量较多的情况时，效率低下。

2.暴力求解优化法：

• 优点：相比暴力排序法，减少了不必要的排序操作，在一定程度上提高了效率。对于一些特定的输入数据，可能会有较好的表现。
• 缺点：时间复杂度仍然较高，每次查找最小元素需要遍历所有链表，当链表数量较多时，效率会受到很大影响。

3.分治法：

• 优点：时间复杂度为 ，相比暴力方法有很大的提升。通过递归地合并链表，充分利用了链表已经升序排列的特点，减少了比较次数。
• 缺点：实现相对复杂，需要理解递归的思想和过程。在处理小规模问题时，可能由于递归调用的开销，效率不一定比其他方法高。

4.堆排序或构建二叉排序树法：

• 优点：时间复杂度为 ，能够快速找到当前最小的元素，保证合并后的链表始终是升序的。对于大规模数据和链表数量较多的情况，具有较好的性能。
• 缺点：需要构建和维护堆或二叉排序树，增加了空间复杂度和实现的复杂性。对于一些简单的场景，可能过于复杂。

（二）未来探索方向

1. 进一步优化时间复杂度：可以探索更高效的算法和数据结构，以降低合并 k 个升序链表的时间复杂度。例如，研究新的分治策略或者改进堆排序的实现，以减少比较次数和操作次数。
2. 空间复杂度的优化：在保证时间效率的同时，尽量降低空间复杂度。可以考虑使用更紧凑的数据结构或者优化算法的内存使用，以减少内存占用。
3. 结合实际应用场景进行优化：根据不同的应用场景，对算法进行针对性的优化。例如，在数据库管理系统中，可以考虑利用数据库的索引结构来加速链表的合并；在图形处理中，可以根据图形的特点和需求，选择合适的合并策略。
4. 并行计算的应用：对于大规模数据和链表数量较多的情况，可以考虑使用并行计算技术，将合并操作分配到多个处理器上同时进行，以提高效率。
5. 动态调整算法：根据输入数据的特点和规模，动态地选择最合适的合并算法。例如，当链表数量较少时，可以使用简单的暴力方法；当链表数量较多时，自动切换到分治或堆排序方法。

        总之，合并 k 个升序链表是一个具有挑战性的问题，通过不断地探索和创新，可以找到更高效、更实用的解决方案，为实际应用提供更好的支持。