题目 在这里插入图片描述题目解析 很明显，这种多个有序链表的排序可以分解为，两个过程：合并两个有序链表的函数。实现多次调用合并两个有序链表。 关于分治法如何优化该过程的？很明显如果直接从左往右调用多次合并两个有序链表来实现需要调用n-1次，而分治法通过先把数组分割成两个数组元素为一个基本的操作对象，那么很明显可以优化为调用logn次。 以下是两种方式的时间差距： 在这里插入图片描述 在这里插入图片描述解题代码 朴素解法class Solution { public: ListNode* mergeKLists(vector<ListNode*>& lists) { int size = lists.size(); if(size==0) return nullptr; ListNode* res = lists[0]; for(int i=1;i<size;i++){ res = mergeTwo(res,lists[i]); } return res; } private: ListNode* mergeTwo(ListNode* a,ListNode* b){ ListNode h; ListNode * head = &h; ListNode* res = head; while(a&&b){ if(a->val>b->val){ head->next = b; b = b->next; head = head->next; }else{ head->next = a; a = a->next; head = head->next; } } if(b){ head->next = b; }else{ head->next = a; } return res->next; } }; 分治法class Solution { public: ListNode* mergeKLists(vector<ListNode*>& lists) { return merge(lists,0,lists.size()-1); } private: ListNode* merge(vector <ListNode*> &lists, int l, int r) { if (l == r) return lists[l]; if (l > r) return nullptr; int mid = (l + r) >> 1; //开始分治 return mergeTwo(merge(lists, l, mid), merge(lists, mid + 1, r)); } ListNode* mergeTwo(ListNode* a,ListNode* b){ ListNode h; ListNode * head = &h; ListNode* res = head; while(a&&b){ if(a->val>b->val){ head->next = b; b = b->next; head = head->next; }else{ head->next = a; a = a->next; head = head->next; } } if(b){ head->next = b; }else{ head->next = a; } return res->next; } };