leetcode 合并K个排序链表 c++实现

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了leetcode 合并K个排序链表 c++实现，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1516字，纯文字阅读大概需要3分钟。

内容图文

??这道题耗时40ms，思路是联想到快慢指针，vector有几个元素，我也有几个头指针，若A的头指针最小，就放入结果指针head的next中，则A就比别的指针快一步，移到下一位next。问题就是判断如何最小，可以自己写，也可以使用priority_queue这样有序的数据结构。感谢博客最下面的链接，我也学到了如何自定义比较器。代码如下：

struct cmp {
    bool operator()(ListNode *&a, ListNode *&b) const {
        return a->val > b->val;
    }
};
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.size() == 0) return nullptr;
        priority_queue<ListNode *, vector<ListNode *>, cmp> q;
        for (int i = 0; i < lists.size(); ++i) {
            if (lists[i] != NULL) {
                q.push(lists[i]);
            }
        }
        ListNode* head = new ListNode(0);
        ListNode* tail = head;
        while (!q.empty()) {
            tail->next = q.top();
            q.pop();
            tail = tail->next;
            if (tail->next != NULL) {
                q.push(tail->next);
            }            
        }
        return head->next;
    }
};

??最快实现代码如下，运用两个链表合并的方式：

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.empty())
            return NULL;
        int len = lists.size();
        while (len > 1) {
            for (int i = 0; i < len / 2; ++i) {
                lists[i] = mergeTwoLists(lists[i], lists[len - 1 - i]);
            }
            len = (len + 1) / 2;
        }
        return lists[0];
    }
    
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode *head = new ListNode(0);
        ListNode *p = head;
        while (l1 && l2) {
            if (l1->val < l2->val) {
                p->next = l1;
                p = l1;
                l1 = l1->next;
            }
            else {
                p->next = l2;
                p = l2;
                l2 = l2->next;
            }
        }
        if (l1)
            p->next = l1;
        else if (l2)
            p->next = l2;
         return head->next;
    }
};

引用与感谢

• https://blog.csdn.net/m0_38015368/article/details/80461938

内容总结

以上是互联网集市为您收集整理的leetcode 合并K个排序链表 c++实现全部内容，希望文章能够帮你解决leetcode 合并K个排序链表 c++实现所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端