php cms网站,主机托管服务,企业建站官网,东莞网站建设企慕思路 解题过程
分治合并 与 LeetCode 21题 合并两个有序链表 相似 只是在此题的基础上增加了链表的数量。 使用递归将链表数组不断分成两半#xff0c;直到分成的小组都只剩下一个链表元素为止#xff0c;随后开始合并链表。 复杂度
时间复杂度: O(N * logK) K 为 链表(li…思路 解题过程
分治合并
与 LeetCode 21题 合并两个有序链表 相似 只是在此题的基础上增加了链表的数量。 使用递归将链表数组不断分成两半直到分成的小组都只剩下一个链表元素为止随后开始合并链表。 复杂度
时间复杂度: O(N * logK) K 为 链表(lists) 的个数n 为所有链表的节点数之和。
空间复杂度: O(logK) 递归的深度为 logK 代码实现
class Solution {public ListNode mergeKLists(ListNode[] lists) {if (lists.length 0)return null;return merge(lists, 0, lists.length - 1);}public ListNode merge(ListNode[] lists, int start, int end) {if (start end)return lists[start];int mid (start end) 1;ListNode pa merge(lists, start, mid);ListNode pb merge(lists, mid 1, end);return mergeSort(pa, pb);}public ListNode mergeSort(ListNode pa, ListNode pb) {ListNode target new ListNode(0);ListNode temp target;while(pa ! null pb ! null){if(pa.val pb.val){temp.next pa;pa pa.next;}else{temp.next pb;pb pb.next;}temp temp.next;}temp.next pa ! null ? pa : pb; return target.next;}
}也可以通过for循环遍历的方式依次合并链表不过时间复杂度会有所提升。
