企业官网建设流程全解析

思路

主要是结合归并排序的思路进行解答，大致就是

1.先二分拆分（merge（）），拆到拆无可拆，也就是左右边界重合为止，至于l>r这种情况，是用来判断空链表这种特殊情况的。

2.然后两两合并（mergeTwoList（）），这个其实是很简单的合并两个有序链表的写法，两两比较，小的放进去，都不用新申请空间。

3.最后逐层向上合并（主函数（）），归并的思路最难的就是这总地方了，想想想🤔💭，上图！！！假如有五个链表的情况（最后的合并阶段实际肯定没这么......将就意思一下吧 大概就这么个理）：

代码

ListNode* mergeTwoList(ListNode* list1, ListNode* list2) { ListNode* dummyhead = new ListNode(); if (!list1 && !list2)return list1 ? list1 : list2; ListNode* p1 = list1, * p2 = list2, * temp = dummyhead; while (p1 && p2) { if (p1->val < p2->val) { temp->next = p1; p1 = p1->next; } else { temp->next = p2; p2 = p2->next; } temp = temp->next; } temp->next = (p1 ? p1 : p2); return dummyhead->next; } ListNode* merge(vector<ListNode*>& lists, int l, int r) { if (l == r)return lists[l]; if (l > r)return nullptr; int mid = (l + r) / 2; return mergeTwoList(merge(lists, l, mid), merge(lists, mid + 1, r)); } class Solution { public: ListNode* mergeKLists(vector<ListNode*>& lists) { return merge(lists, 0, lists.size() - 1); } };

小复习

归并排序

-核心思想：先拆分，后合并

（1）分：递归把数组从中间切为左右两半，一直切到子区间只有 1 个元素

（2）治（合并）：将两个已经有序的子数组，用双指针合并成一个有序数组

（3）逐层向上合并，最后整个数组有序

-归并排序代码（C++版本)

void merge(vector<int>& arr, int l, int mid, int r) { vector<int> tmp; int i = l, j = mid+1; while(i <= mid && j <= r) { if(arr[i] < arr[j]) tmp.push_back(arr[i++]); else tmp.push_back(arr[j++]); } while(i <= mid) tmp.push_back(arr[i++]); while(j <= r) tmp.push_back(arr[j++]); // 拷贝回原数组 for(int k = 0; k < tmp.size(); k++) arr[l + k] = tmp[k]; } void mergeSort(vector<int>& arr, int l, int r) { if(l >= r) return; int mid = l + (r-l)/2; mergeSort(arr, l, mid); // 左半部分排序 mergeSort(arr, mid+1, r); // 右半部分排序 merge(arr, l, mid, r); // 合并两个有序区间 }

-复杂度

（1）时间复杂度：O(nlog n)，是稳定排序

（2）空间复杂度：O(n)