多个有序链表的有序合并【C++】暴力合并排序后相连（使用vector和sort）分治法递归解决

63 阅读 0 评论 42 点赞

我是靠谱客的博主听话飞鸟，最近开发中收集的这篇文章主要介绍多个有序链表的有序合并【C++】暴力合并排序后相连（使用vector和sort）分治法递归解决，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

问题描述:合并 k 个排序链表，返回合并后的排序链表
可以有三个办法，在此问题上的基础是进行两个链表的合并，代码如下：

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

// 合并两个有序链表
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    ListNode temp_head(0);
    ListNode* pre = &temp_head;
    while (l1 && l2)
    {
        if (l1->val < l2->val) {
            pre->next = l1;
            l1 = l1->next;
        }
        else {
            pre->next = l2;
            l2 = l2->next;
        }
        pre = pre->next;
    }
    if (l1)
    {
        pre->next = l1;
    }
    if (l2)
    {
        pre->next = l2;
    }
    return temp_head.next;
}

暴力合并

直接把第一个链表和第二个链表用两个链表有序合并的方法mergeTwoLists合并为链表new1，再把new和第三个链表合并为new2，以此类推，但此类算法时间复杂度不好，略过…

排序后相连（使用vector和sort）

方法：把所有节点存入vector然后排序

先演示sort的基本实现：

bool cmp(const ListNode* a, const ListNode* b) {
    return a->val < b->val;
}

int main() {
    ListNode a(3);
    ListNode b(2);
    ListNode c(5);
    ListNode d(0);
    vector<ListNode*> node_vec;
    node_vec.push_back(&a);
    node_vec.push_back(&b);
    node_vec.push_back(&c);
    node_vec.push_back(&d);
    sort(node_vec.begin(), node_vec.end(), cmp);
    for (int i = 0; i < node_vec.size(); i++)
    {
        cout << node_vec[i]->val << endl;
    }
    return 0;
}

解决问题：

// 算法写在一个类里
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        vector<ListNode*> node_vec;
        ListNode* head = NULL;
        for (int i = 0; i < lists.size(); i++)
        {
            // 取出每一个链表的结点存入新的vector
            head = lists[i];
            while (head)
            {
                node_vec.push_back(head);
                head = head->next;
            }
        }
        if (node_vec.size() == 0) {
            return NULL;
        }
        sort(node_vec.begin(), node_vec.end(), cmp);
        for (int i = 1; i < node_vec.size(); i++)
        {
            node_vec[i - 1]->next = node_vec[i]; //新链表连接
        }
        node_vec[node_vec.size() - 1]->next = NULL;
        return node_vec[0];
    }
};

分治法递归解决

把k个链表每次2分化成最终为两个链表的合并，代码如下：

// 算法写在一个类里
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.size() == 0)
            return NULL;
        if(lists.size() == 1)
            return lists[0];
        if (lists.size() == 2)
            return mergeTwoLists(lists[0], lists[1]);
        int mid = lists.size() / 2;

        // 拆分为两个子list
        vector<ListNode*> sub1_lists;
        vector<ListNode*> sub2_lists;
        for (int i = 0; i < mid; i++)
        {
            sub1_lists.push_back(lists[i]);
        }
        for (int i = mid; i < lists.size(); i++)
        {
            sub2_lists.push_back(lists[i]);
        }
        ListNode* l1 = mergeKLists(sub1_lists);
        ListNode* l2 = mergeKLists(sub2_lists);
        return mergeTwoLists(l1, l2); // 分治处理
    }
};


// 以下为测试
int main() {
    ListNode a(1);
    ListNode b(4);
    ListNode c(6);
    ListNode d(0);
    ListNode e(5);
    ListNode f(7);
    ListNode g(2);
    ListNode h(3);
    a.next = &b;
    b.next = &c;
    d.next = &e;
    e.next = &f;
    g.next = &h;
    Solution solve;
    vector<ListNode*> lists;
    lists.push_back(&a);
    lists.push_back(&d);
    lists.push_back(&g);
    ListNode* head = solve.mergeKLists(lists);
    while (head)
    {
        cout << head->val << endl;
        head = head->next;
    }

    return 0;
}