LeetCode 刷题【23. 合并 K 个升序链表】

23. 合并 K 个升序链表

自己做

归并实现1：两两归并

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:

    ListNode* getMerge(ListNode* list1, ListNode* list2){           //两有序链表合并
        ListNode *p = list1, *q = list2;
        ListNode *res = new ListNode();
        ListNode *k = res;

        while(p != nullptr && q != nullptr){                    //合并两有序
            if(p->val < q->val){                                //p指向的更小
                k->next = p;
                p = p->next;
            }
            else{                                                //q指向的更小
                k->next = q;
                q = q->next;
            }

            k = k->next;                                        //k指向尾部
            k->next = nullptr;

        }

        while(p != nullptr){                                //p没有遍历完
            k->next = p;
            p = nullptr;
        }

        while(q != nullptr){                                //q没有遍历完
            k->next = q;
            q = nullptr;
        }
        
        return res->next;
    }

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        int len = lists.size();                 //有多少个链表

        if(len == 0)                            //空链表不处理     
            return nullptr;

        if(len == 1)                            //只有一个链表，直接返回
            return lists[0];

        while(len > 1){
            lists[1] = getMerge(lists[0],lists[1]); //两个有序链表合并为一个

            lists.erase(lists.begin());

            len = lists.size();                     //合并后链表数组的长度更新
        }

        return lists[0];

    }
};

归并实现2：从上往下扫描

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        int len = lists.size();                 //有多少个链表

        ListNode* res = new ListNode();
        ListNode* k = res;

        //首先消除所有的空链表

        for (vector<ListNode*>::iterator it = lists.begin(); it != lists.end(); ) {   //从上往下扫描
            if ((*it) == nullptr) {        //it所指向的空间存放的链表为空
                it = lists.erase(it);            //消除
            }
            else
                it++;
        }

        len = lists.size();         //更新长度

        if (len == 0)                        //空链表数组直接返回
            return nullptr;

        while (len > 1) {                     //只要是大于两个链表就一直扫描
            int q = 0;                      //最小值所指向的p索引下标
            int min = lists[0]->val;            //设置当轮的最小值

            for (int i = 0; i < len; i++) {   //从上往下扫描
                if (lists[i]->val < min) {
                    min = lists[i]->val;
                    q = i;
                }
            }

            //扫描结束找到当轮的最小值
            k->next = lists[q];
            lists[q] = lists[q]->next;
            k = k->next;
            k->next = nullptr;

            if (lists[q] == nullptr) {        //lists[q]所指向的链表已经完全取完
                //删除该位置的指针
                vector<ListNode*>::iterator it = lists.begin();

                for (int i = 0; i < q; i++)
                    it++;

                lists.erase(it);

                //更新长度
                len = lists.size();
            }

        }

        //此时只剩下一个链表lists[0]
        k->next = lists[0];

        return res->next;

    }
};

看题解

优先队列

class Solution {
public:
    struct Status {
        int val;
        ListNode *ptr;
        bool operator < (const Status &rhs) const {
            return val > rhs.val;
        }
    };

    priority_queue <Status> q;

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        for (auto node: lists) {
            if (node) q.push({node->val, node});
        }
        ListNode head, *tail = &head;
        while (!q.empty()) {
            auto f = q.top(); q.pop();
            tail->next = f.ptr; 
            tail = tail->next;
            if (f.ptr->next) q.push({f.ptr->next->val, f.ptr->next});
        }
        return head.next;
    }
};

今日总结

除了归并完全想不到其他方法