Leetcode 23. 合并 K 个升序链表

Leetcode 23. 合并 K 个升序链表

**题目描述：**给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。

分治思想

方法一：顺序合并

两两合并，用一个变量res 来维护以及合并的链表，第 i 次循环把第 i 个链表和res合并，答案保存到 res 中。

/**
 * 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* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(!l1) {
            return l2;
        }
        if(!l2) {
            return l1;
        }
        ListNode* dummyHead = new ListNode();
        ListNode* cur = dummyHead;
        while(l1 && l2) {
            if(l1->val < l2->val) {
                cur->next = l1;
                l1 = l1->next;
            }
            else {
                cur->next = l2;
                l2 = l2->next;
            }
            cur = cur->next;
        }
        if(l1) {
           cur->next = l1; 
        }
        if(l2) {
            cur->next = l2;
        }
        ListNode* head = dummyHead->next;
        delete dummyHead;
        dummyHead = nullptr;
        return head;
    } 

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        size_t len = lists.size();
        if(!len) {
            return nullptr;
        }
        ListNode* res = nullptr;
        for(size_t i = 0; i < len; ++i) {
            res = mergeTwoLists(res, lists[i]);
        }
        return res;
    }
};

方法二：分治合并


/**
 * 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* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(!l1) {
            return l2;
        }
        if(!l2) {
            return l1;
        }
        ListNode* dummyHead = new ListNode();
        ListNode* cur = dummyHead;
        while(l1 && l2) {
            if(l1->val < l2->val) {
                cur->next = l1;
                l1 = l1->next;
            }
            else {
                cur->next = l2;
                l2 = l2->next;
            }
            cur = cur->next;
        }
        if(l1) {
           cur->next = l1; 
        }
        if(l2) {
            cur->next = l2;
        }
        ListNode* head = dummyHead->next;
        delete dummyHead;
        dummyHead = nullptr;
        return head;
    } 

    ListNode* mergeList(vector<ListNode*>& lists, int left, int right) {
        if(left == right) { //切记不要写=
            return lists[left];
        }
        if(left > right) {
            return nullptr;
        }
        size_t middle = left + (right - left) / 2;
        ListNode* list1 = mergeList(lists, left, middle);
        ListNode* list2 = mergeList(lists, middle + 1, right);
        return mergeTwoLists(list1, list2);
    }

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        size_t len = lists.size();
        if(!len) {
            return nullptr;
        }
        ListNode* res = nullptr;
        for(size_t i = 0; i < len; ++i) {
            res = mergeTwoLists(res, lists[i]);
        }
        return res;

    }
};

优先队列

合并 k 个有序链表的逻辑类似合并两个有序链表，难点在于，如何快速得到 k 个节点中的最小节点，接到结果链表上？

这里我们就要用到 优先级队列（二叉堆） 这种数据结构，把链表节点放入一个最小堆，就可以每次获得 k 个节点中的最小节点

/**
 * 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) {
        if(lists.empty()) {
            return nullptr;
        }
        
        ListNode* dummyHead = new ListNode();
        ListNode* cur = dummyHead;

        auto cmp = [](ListNode* l1, ListNode* l2) {
            return l1->val > l2->val;   //使用小根堆
        };  //记得这里有`;`
        priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq(cmp);
        for(auto head : lists) { 
            if(head != nullptr) {   //注意：这里要判断是否遍历完成
                pq.push(head);  //将头结点压入队列
            }   
            
        }

        while(!pq.empty()) {
            ListNode* minNode = pq.top(); pq.pop();
            cur->next = minNode;
            if(minNode->next) { //所在list还有元素，将下一个结点做这个list的head压入队列
                pq.push(minNode->next);
            }
            cur = cur->next;
        }
        return dummyHead->next;
    }
};

C++ priority_queue 与 lambda的结合使用

class student{
 public:
     int age;
     string name;
     /**重载小于操作符，
	      *这里必须是非成员函数才可以
		*/
     friend bool operator<(const student& a, const student & b){
         return a.age < b.age;
     }
};

/**可调用的函数操作符的对象*/
struct mycmp{
 bool operator()(const student & a,const student & b){
     return a.age < b.age;
 }
};

/**函数指针*/
bool cmpfunc(const student& a, const student& b){
 return a.age < b.age;
}

/**默认使用student的oprator<来进行比较*/
priority_queue<student> que1;

/**使用重载函数操作符的类对象*/
priority_queue<student,vector<student>,mycmp> que2;

/**定义一下比较函数*/
auto cmp = [](const student & a,const student & b){return a.age < b.age;};
/**
  *	需要把lambda表达式作为优先队列参数进行初始化
  * 并且指定priority_queue的模板实参，decltype(cmp)，c++11 declare type，声明类型
  * 可以认为是确定函数的类型
  * bool (const student & a,const student & b)
  **/
priority_queue<student,vector<student>,decltype(cmp)> que4(cmp);

/*使用函数对象来定义这个比较函数原型*/
//lambda 函数来初始化函数对象
priority_queue<student,vector<student>,function<bool(const student&,const student&)>> que5(cmp);

//函数指针来初始化函数对象
priority_queue<student,vector<student>,function<bool(const student&,const student&)>> que6(cmpfunc);

/**函数对象*/
function<bool(const student&,const student &)> func(cmpfunc);
priority_queue<student,vector<student>,function<bool(const student&,const student&)>> que7(func);