原题链接

讨论澄清

此题是在合并两条链表的基础上，扩展成多条链表的，因此我们就应该将他再次细分成两条链表的合并的思路来处理，再将K条链表分解成两条两条链表的合并这个过程要利用分治的思想。

思路简述

注意事项

具体代码

  1. class Solution {
  4.     /**
  5.     结合昨天的合并两个链表的方法，对链表进行分治，利用递归的方法转化为两个两个链表的合并
  7.      */
  8.     public ListNode mergeKLists(ListNode[] lists) {
  9. return merge(lists, 0, lists.length - 1);
  10.     }
  13.     public ListNode merge(ListNode[] list,int begin,int end){
  14.         //如果数组中只有一组链表 那么就只返回一组数据
  15.         if(begin==end){
  16.             return list[begin];
  17.         }
  18.             //元素为空则返回空
  19.         if(begin>end){
  20.             return null;
  21.         }
  22.         //两组数据以上的情况，进行分治、两组两组的合并
  23.         int mid = (begin+end)/2;
  24.         return mergeTwoLists(merge(list,begin,mid),merge(list,mid+1,end));
  26.     }
  30. //两组合并的方法完全照抄昨天的题解：合并两个有序链表的代码
  31.     public ListNode mergeTwoLists(ListNode l1,ListNode l2){
  32.         ListNode dummyhead = new ListNode();
  33.         ListNode newnode = new ListNode();
  34.         dummyhead = newnode;
  35.         while(l1!=null&&l2!=null){
  36.             if(l1.val<=l2.val){
  37.                 newnode.next = l1;
  38.                 l1 = l1.next;
  39.             }else{
  40.                 newnode.next = l2;
  41.                 l2 = l2.next;
  42.             }
  43.             newnode = newnode.next;
  44.         }
  46.  //如果链表l1先合并完，那么就把l2剩余的节点接在合并的链表末尾
  48.  if(l1==null){
  49.             newnode.next = l2;
  50.             while(l2!=null){
  51.                 newnode = newnode.next;
  52.                 l2 = l2.next;
  53.             }
  54.         }
  55.   //如果链表l2先合并完，那么就把剩余的节点接在合并的链表末尾
  57.   if(l2==null){
  58.             newnode.next = l1;
  59.             while(l1!=null){
  60.                 newnode = newnode.next;
  61.                 l1 = l1.next;
  62.             }
  64.         }
  66.         return dummyhead.next;
  68.     }
  71. }