23. 合并K个排序链表

方法1 排序

来源
sort的写法值得学习，使用了lambda表达式，很多题应该流氓点可以靠 sort解决

class Solution {
    public:
        ListNode* mergeKLists(vector<ListNode*>& lists) {
            vector<ListNode*> longList;
            for (ListNode* start:lists) {
                ListNode* ptr = start;
                while (ptr != NULL) {
                    longList.push_back(ptr);
                    ptr = ptr->next;
                }
            }
            std::sort(longList.begin(),longList.end(),[](auto x,auto y) {
                return ((x->val) < (y->val));
            });
            if (longList.size() ==0) {
                return NULL;
            }
            for (size_t i=0; i<longList.size()-1; i++) {
                longList[i]->next = longList[i+1];
            }
            longList[longList.size()-1]->next = NULL;
            return longList[0];
        }
};

方法2 分治

C++代码：

class Solution {
    public:
        ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
            ListNode *p=new ListNode(0);
            ListNode *head=p;
            while(l1 && l2) {
                if(l1->val<l2->val) {
                    p->next=l1;
                    p=p->next;
                    l1=l1->next;
                } else {
                    p->next=l2;
                    p=p->next;
                    l2=l2->next;
                }
            }
            while(l1) {
                p->next=l1;
                p=p->next;
                l1=l1->next;
            }
            while(l2) {
                p->next=l2;
                p=p->next;
                l2=l2->next;
            }
            p->next=NULL;
            return head->next;
        }

        ListNode* mergeKLists(vector<ListNode*>& lists) {
            if(lists.size()==0) return NULL;
            else if(lists.size()==1) return lists[0];
            else if(lists.size()==2) return mergeTwoLists(lists[0],lists[1]);
            int mid=lists.size()/2;
            vector<ListNode*>sub_list1;
            vector<ListNode*>sub_list2;
            for(int i=0;i<mid;i++){
                sub_list1.push_back(lists[i]);
            }
            for(int i=mid;i<lists.size();i++){
                sub_list2.push_back(lists[i]);
            }
            ListNode *l1=mergeKLists(sub_list1);
            ListNode *l2=mergeKLists(sub_list2);
            return mergeTwoLists(l1,l2);
        }
};