给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 1：
输入：lists = [[1,4,5],[1,3,4],[2,6]] 输出：[1,1,2,3,4,4,5,6] 解释：链表数组如下： [ 1->4->5, 1->3->4, 2->6 ] 将它们合并到一个有序链表中得到。 1->1->2->3->4->4->5->6示例 2：
输入：lists = [] 输出：[] 示例 3： 输入：lists = [[]] 输出：[]我的理解是先合并两个 然后依次遍历合并n个 根据这个思路就是 先写个add2函数然后遍历数组 得到答案
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode mergeKLists(ListNode[] lists) { //依次遍历 亮亮合并 ListNode res = null; for (ListNode list : lists) { res = add2(res,list); } return res; } public ListNode add2(ListNode l1, ListNode l2){ //合并两个有序链表 ListNode dum = new ListNode(0); ListNode tail = dum; while (l1 != null && l2 != null){ if(l1.val < l2.val){ tail.next = l1; l1 = l1.next; tail = tail.next; }else { tail.next = l2; l2 = l2.next; tail = tail.next; } } //长度不一样有链表为空 tail.next = l1 == null ? l2 : l1; return dum.next; } }很明显 效率很低 所以有另一种思路并归或者叫分治，每次两两一合并 同时进行
class Solution { public ListNode mergeKLists(ListNode[] lists){ if(lists.length == 0) return null; if(lists.length == 1) return lists[0]; if(lists.length == 2){ return mergeTwoLists(lists[0],lists[1]); } int mid = lists.length/2; ListNode[] l1 = new ListNode[mid]; for(int i = 0; i < mid; i++){ l1[i] = lists[i]; } ListNode[] l2 = new ListNode[lists.length-mid]; for(int i = mid,j=0; i < lists.length; i++,j++){ l2[j] = lists[i]; } return mergeTwoLists(mergeKLists(l1),mergeKLists(l2)); } public ListNode mergeTwoLists(ListNode l1, 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; } }偷别人的答案 日后再刷
