(链表，分治，优先队列) leetcode 23.Merge K Sorted Lists

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        //priority_queue
        ListNode dummy(0);   //新建一个头结点，值为0
        ListNode *tail = &dummy;
        
        auto cmp = [](ListNode* a, ListNode* b){return a->val > b->val; };   //从小到大排序
        priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> q(cmp);
        
        for(ListNode* list : lists)
            if(list)
                q.push(list);   //将vector中的链表放入队列q中，即将三个链表的头指针放到q中
        
        while(!q.empty()){
            tail->next = q.top();
            q.pop();
            tail = tail->next;   //tail指向当前元素
            if(tail->next)
                q.push(tail->next);
        }
        return dummy.next;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return merge(lists, 0, lists.size()-1);
    }
    
    ListNode* merge(vector<ListNode*>& lists, int l, int r){
        //递归
        if(l > r)
            return NULL;
        if(l == r)
            return lists[l];  //lists里只有一个list
        if(l+1 == r)
            return mergeTwoLists(lists[l], lists[r]);  //lists里有两个list
        int m = l+(r-l)/2;
        auto l1 = merge(lists, l, m);
        auto l2 = merge(lists, m+1, r);
        return mergeTwoLists(l1, l2);
    }
    
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2){
        ListNode dummy(0);
        ListNode* tail = &dummy;
        while(l1 && l2){
            if(l1->val > l2->val)
                swap(l1, l2);  //l1指向val小的结点
            tail->next = l1;  
            l1 = l1->next;
            tail = tail->next;
        }
        tail->next = l1? l1 : l2;
        return dummy.next;
    }
};