23. 合并K个升序链表

难度困难1897收藏分享切换为英文接收动态反馈
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 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 = [[]] 输出：[]

提示：

  • k == lists.length
  • 0 <= k <= 10^4
  • 0 <= lists[i].length <= 500
  • -10^4 <= lists[i][j] <= 10^4
  • lists[i] 按 升序 排列
  • lists[i].length 的总和不超过 10^4

使用二分法合并:

  1. /**
  2.  * Definition for singly-linked list.
  3.  * public class ListNode {
  4.  *     int val;
  5.  *     ListNode next;
  6.  *     ListNode(int x) { val = x; }
  7.  * }
  8.  */
  9. class Solution {
  10.     private ListNode merge(ListNode l1,ListNode l2)
  11.     {
  12.         ListNode head=new ListNode(0);
  13.         ListNode tail=head;
  14.         while(l1!=null&&l2!=null)
  15.         {
  16.             if(l1.val<l2.val)
  17.             {
  18.                 tail.next=l1;
  19.                 tail=tail.next;
  20.                 l1=l1.next;
  21.             }
  22.             else
  23.             {
  24.                 tail.next=l2;
  25.                 tail=tail.next;
  26.                 l2=l2.next;
  27.             }
  28.         }
  29.         if(l1!=null)
  30.             tail.next=l1;
  31.         if(l2!=null)
  32.             tail.next=l2;
  33.         return head.next;
  35.     }
  36.     private ListNode helper(ListNode[] lists,int lo,int hi)
  37.     {
  38.         if(lo>hi)
  39.             return null;
  40.         if(lo==hi)
  41.             return lists[lo];
  43.         int mid=(lo+hi)/2;
  44.         ListNode l1=helper(lists,lo,mid);
  45.         ListNode l2=helper(lists,mid+1,hi);
  46.         return merge(l1,l2);
  47.     }
  49.     public ListNode mergeKLists(ListNode[] lists) {
  50.         return helper(lists,0,lists.length-1);
  51.     }
  53. }