Leetcode_23 题目
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
以下为示例：
Example 1
输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6
Example 2
输入：lists = []
输出：[]
Example 3
输入：lists = [[]]
输出：[]
提示：
k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] 按 升序 排列
lists[i].length 的总和不超过 10^4
个人解答及思路
代码如下：
class Solution {
public:
void mergeSort(int arr[], int arrSize){
if (arr == NULL || arrSize < 2) return;
process(arr, 0, arrSize - 1);
}
void process(int arr[], int L, int R){
if (L == R) return;
int mid = L + (R - L) / 2;
process(arr, L, mid);
process(arr, mid + 1, R);
merge(arr, L, mid, R);
}
void merge(int arr[], int L, int M, int R){
int *new_arr = new int[R - L + 1];
int p1 = L, p2 = M + 1, cnt = 0;
while (p1 <= M && p2 <= R){
new_arr[cnt++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
}
while (p1 <= M) new_arr[cnt++] = arr[p1++];
while (p2 <= R) new_arr[cnt++] = arr[p2++];
for (int i = 0; i < cnt; i++){
arr[L + i] = new_arr[i];
}
}
ListNode* mergeKLists(vector<ListNode*>& lists){
ListNode* head = new ListNode;
if (lists.size() == 0){
head->next = nullptr;
return head->next;
}
vector<int>arr_v;
for (vector<ListNode*>::iterator iter = lists.begin();
iter != lists.end(); ++iter){
ListNode* list = (*iter);
while (list){
arr_v.push_back(list->val);
list = list->next;
}
}
int *arr = new int[arr_v.size()];
int cnt = 0;
for (int num : arr_v){
arr[cnt++] = num;
}
mergeSort(arr, arr_v.size());
int i = 0;
ListNode* pre_ptr = head, *now_ptr;
while (i < arr_v.size()){
now_ptr = new ListNode;
now_ptr->next = nullptr;
now_ptr->val = arr[i++];
pre_ptr->next = now_ptr;
pre_ptr = now_ptr;
}
return head->next;
}
};
新代码（利用双进行遍历指针，较归并差）
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
vector<ListNode*> all_list;
if (lists.size() == 0) return nullptr;
all_list.push_back(*(lists.begin()));
for (auto iter = lists.begin(); iter != lists.end(); iter++){
vector<ListNode*> new_list;
if (iter == lists.begin()) continue;
ListNode* nowp = all_list[0];
ListNode* addi = (*iter);
while (nowp && addi){
if (nowp->val < addi->val){
new_list.push_back(nowp);
nowp = nowp->next;
}
else{
new_list.push_back(addi);
addi = addi->next;
}
}
while (nowp){
new_list.push_back(nowp);
nowp = nowp->next;
}
while (addi){
new_list.push_back(addi);
addi = addi->next;
}
for (auto i = 0; i != new_list.size(); i++){
if (i != new_list.size() - 1) new_list[i]->next = new_list[i+1];
else new_list[i]->next = nullptr;
}
all_list = new_list;
}
return all_list[0];
}
};
注：该代码并不能完全通过Leetcode，因为时间复杂度过高，优化的思想是通过利用mergeSort的思想，将总的vector容器进行归并，得到最终的总排列，但是由于基础较差，只能先写到这里，对容器进行归并还需一段时间的学习
思路
对于本题，我首先想到的方法是直接将所有数据暴力提取，然后利用稳定的归并排序，写完
之后意识到可以通过利用循环把已排序的链表，采取类似多指针的方式遍历所有的链表得到最终
的链表。
此篇代码中，先构建头指针，然后判断是否存在元素。因为示例中出现两种空链表的情况，
所以需要着重考虑一下对代码的分析，分为两种情况：1、本身就无链表。2、链表为空。
所以先判定链表存在，然后利用暴力将所有数据提取到arr_v容器中，后续利用归并排
序得到目标数组，之后再重新构建链表输出。
说实话，这样的方法很蠢，明天我试一下多指针的方法。如有疑点，麻烦各位指正，相互学
习。
代码总结
本篇代码纯不动脑子的乱写，还请见谅，代码量过大，但是期间我也学到了不少东西，比如
最后的时候，没有初始化链表的指针nullptr会出现报错，其实并没逻辑问题，只是编译器上无法
接受；还有之前并没有用new进行内存分配，而是用malloc，之后就发生了不明的报错，于是不用
malloc改用new。对于此类问题，我觉得虽然解法繁琐，但是可以巩固之前学过的知识，也是一种
学习方式。
|