思路主要是结合归并排序的思路进行解答大致就是1.先二分拆分merge拆到拆无可拆也就是左右边界重合为止至于lr这种情况是用来判断空链表这种特殊情况的。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(vectorListNode* 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(vectorListNode* lists) { return merge(lists, 0, lists.size() - 1); } };小复习归并排序-核心思想先拆分后合并1分递归把数组从中间切为左右两半一直切到子区间只有 1 个元素2治合并将两个已经有序的子数组用双指针合并成一个有序数组3逐层向上合并最后整个数组有序-归并排序代码C版本)void merge(vectorint arr, int l, int mid, int r) { vectorint tmp; int i l, j mid1; 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(vectorint arr, int l, int r) { if(l r) return; int mid l (r-l)/2; mergeSort(arr, l, mid); // 左半部分排序 mergeSort(arr, mid1, r); // 右半部分排序 merge(arr, l, mid, r); // 合并两个有序区间 }-复杂度1时间复杂度O(nlog n)是稳定排序2空间复杂度O(n)
思路主要是结合归并排序的思路进行解答大致就是1.先二分拆分merge拆到拆无可拆也就是左右边界重合为止至于lr这种情况是用来判断空链表这种特殊情况的。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(vectorListNode* 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(vectorListNode* lists) { return merge(lists, 0, lists.size() - 1); } };小复习归并排序-核心思想先拆分后合并1分递归把数组从中间切为左右两半一直切到子区间只有 1 个元素2治合并将两个已经有序的子数组用双指针合并成一个有序数组3逐层向上合并最后整个数组有序-归并排序代码C版本)void merge(vectorint arr, int l, int mid, int r) { vectorint tmp; int i l, j mid1; 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(vectorint arr, int l, int r) { if(l r) return; int mid l (r-l)/2; mergeSort(arr, l, mid); // 左半部分排序 mergeSort(arr, mid1, r); // 右半部分排序 merge(arr, l, mid, r); // 合并两个有序区间 }-复杂度1时间复杂度O(nlog n)是稳定排序2空间复杂度O(n)
