1. 题目描述
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Example:
Input:
[
1->4->5,
1->3->4,
2->6
]
Output: 1->1->2->3->4->4->5->62. 初解
这题毫无疑问是上次合并两个有序链表的加强版，难度也从Easy直接上升到了Hard，看了一下午也终归是AC了，也是AC的第一道Hard，撒花★,°:.☆(￣▽￣)/$:.°★ 。
我首先想到，既然和那道合并两个有序链表那么相似，那我完全可以用类似的方法，只不过那道题只有两个有序链表，所以我每次只用比较这两个链表的头节点然后将数值较小的节点接在新链表后面。而这个题由于有k个有序链表，所以我理论上一次要比较k个头节点然后找出最小节点，所以最好创建一个长度为k的数组来装k个头结点的数值方便比较。然后那道题由于只有两个有序链表，所以只需要两个指针 l1 和 l2 来记录两个链表现在的头节点，每找出一个较小节点，就将这个节点对应链表的指针等于自己的next，从而实现指针后移。而现在这道题，k个有序链表，毫无疑问无法直接列出指向每个链表的指针 l1 l2 ... lk ，那就只好换个方法。建立一个二级指针struct ListNode** ptrList;
而让二级指针指向每一个有序链表的节点，从而实现一次管理k个指针。
大的问题基本上已经解决了，还剩一些小细节。合并两个有序链表的时候，一个链表遍历完了，直接让另一个链表接在新链表后面就行了。但我们这道题由于有k个链表，所以没办法这么简单粗暴。我采用的方法是，如果一个链表遍历完了，就将这个链表对应的数组项置为int最大值，并且用一个变量count记录已经遍历完的链表个数。当count等于链表总个数的时候直接结束就ok了。
基本逻辑就是这样，现在分析一下时间复杂度。
可以知道，假设有k个有序链表，我们每次就要比较k个元素从而选出最小的那个节点，而假如k个链表中总共有N个节点，那么得到最终的长度为N的新链表所需要的时间就是 O(kN)，即为时间复杂度。
3. 代码
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
// #define DEBUG
struct ListNode {
int val;
struct ListNode* next;
};
// 找到数组中最小元素的下标
int findMinIndex(int* arr, int size) {
int index = 0;
int min = arr[index];
#ifdef DEBUG
printf("arr[0] = %d\n", arr[0]);
system("pause");
#endif // DEBUG
for (int i = 1; i <= size - 1; i++) {
#ifdef DEBUG
printf("arr[%d] = %d\n", i, arr[i]);
system("pause");
#endif // DEBUG
if (arr[i] < min) {
index = i;
min = arr[index];
}
}
return index;
}
struct ListNode* mergeKLists(struct ListNode** lists, int listsSize) {
int count = 0; // 记录已经遍历完的数组的个数，方便结束程序
// 建立待比较数组
int* arr = (int *)malloc(sizeof(int) * listsSize);
for (int i = 0; i < listsSize; i++) {
if (lists[i] == NULL) {
arr[i] = INT_MAX;
count++;
}
else {
arr[i] = lists[i]->val;
}
}
if (count == listsSize) // 如果传进来的全部是空链表，返回NULL
return NULL;
// 为每个链表建立指针
struct ListNode** ptrList = lists;
// 建立要返回的结果指针
struct ListNode* res =
(struct ListNode *)malloc(sizeof(struct ListNode));
res->next = NULL;
struct ListNode* ptr = res;
// 开始比较
int index;
while (1) {
// 找出所有数中最小的数的索引
index = findMinIndex(arr, listsSize);
#ifdef DEBUG
printf("index = %d\n", index);
system("pause");
#endif // DEBUG
// 将这个节点接在res上
ptr->next = ptrList[index];
ptr = ptr->next;
// 将最小数所在的链表的指针向后移，要考虑这是不是当前链表的最后一个节点
// 如果是最后一个节点，则把对应这个链表的数组元素置为INT_MAX
if (ptrList[index]->next == NULL) {
arr[index] = INT_MAX;
count++;
#ifdef DEBUG
printf("count %d\n", count);
#endif // DEBUG
}
else {
ptrList[index] = ptrList[index]->next;
arr[index] = ptrList[index]->val;
}
if (count == listsSize) { // 如果全部链表都遍历完了，退出循环
ptr->next = NULL;
break;
}
#ifdef DEBUG
printf("count = %d\n", count);
system("pause");
#endif // DEBUG
}
return res->next;
}
struct ListNode* createLL(int* arr, int size) {
struct ListNode* res =
(struct ListNode *)malloc(sizeof(struct ListNode));
res->next = NULL;
struct ListNode* ptr = res;
struct ListNode* tmp;
for (int i = 0; i < size; i++) {
tmp = (struct ListNode *)malloc(sizeof(struct ListNode));
tmp->val = arr[i];
tmp->next = NULL;
ptr->next = tmp;
ptr = ptr->next;
}
return res->next;
}
void printLL(struct ListNode* head) {
struct ListNode* ptr = head;
while (ptr) {
printf("%d -> ", ptr->val);
ptr = ptr->next;
}
putchar('\n');
}
int main() {
int arr1[5] = { 1, 4, 7, 8, 9 };
int arr2[3] = { 2, 4, 6 };
int arr3[7] = { 11, 12, 13, 14, 15, 16, 17 };
struct ListNode* ptr1 = createLL(arr1, sizeof(arr1) / sizeof(int));
struct ListNode* ptr2 = createLL(arr2, sizeof(arr2) / sizeof(int));
struct ListNode* ptr3 = createLL(arr3, sizeof(arr3) / sizeof(int));
struct ListNode** pptr =
(struct ListNode **)malloc(sizeof(struct ListNode *) * 3);
pptr[0] = ptr1;
pptr[1] = ptr2;
pptr[2] = ptr3;
struct ListNode* res = mergeKLists(pptr, 3);
printLL(res);
system("pause");
return 0;
}