Leetcode刷题_23 合并K个升序链表（基于C++）Leetcode_23 题目

50 阅读 0 评论 33 点赞

我是靠谱客的博主傲娇音响，最近开发中收集的这篇文章主要介绍Leetcode刷题_23 合并K个升序链表（基于C++）Leetcode_23 题目，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

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。对于此类问题，我觉得虽然解法繁琐，但是可以巩固之前学过的知识，也是一种
学习方式。