50题 第13天 合并K个有序列表

• 合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。（昨天题的衍生）
• 链接: 力扣.
• 我的代码如下：

/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/
class Solution {public ListNode mergeKLists(ListNode[]lists) {ListNode result= new ListNode(0);if(lists==null || lists.length==0){return null;}else if(lists.length==1){return lists[0];}else if(lists.length==2){result=mergeTwoLists(lists[0],lists[1]);}else{result=mergeTwoLists(lists[0],lists[1]);for(int i=2;i<lists.length;i++){result=mergeTwoLists(result,lists[i]);}}return result;}public ListNode mergeTwoLists(ListNodel1,ListNode l2) {if(l1==null){return l2;}if(l2==null){return l1;  }    ListNode head = null;if(l1.val <= l2.val){head = l1;head.next =mergeTwoLists(l1.next,l2);}else{head = l2;head.next =mergeTwoLists(l1,l2.next);}return head;}  }

运行结果

• 今天的题本身就是对昨天题的一个提升，也算是为了偷懒，我的思路是先照搬昨天两个链表排序的方法，然后把k个转化为前k-1个和下一个这种方法递归上去，这样是可以实现的。但是因为本来昨天用的也是递归的办法，相当于用了两次递归，时间复杂性就很高，用时和内存都很不理想，暂时没有什么解决办法，感觉要改就要另起炉灶，看看大佬的做法吧。