力扣 LCR 078 合并K个升序链表

思路 + 解题过程

分治合并

与 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循环遍历的方式依次合并链表，不过时间复杂度会有所提升。