非常经典的一道题目了

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例

输入:
[
1->4->5,
1->3->4,
2->6
]
输出: 1->1->2->3->4->4->5->6

/**  * Definition for singly-linked list.  * public class ListNode {  *     int val;  *     ListNode next;  *     ListNode(int x) { val = x; }  * }  */ class Solution {   //mergeKlist方法主要是按照归并排序的思想将数组进行分割     public ListNode mergeKLists(ListNode[] lists) {     //如果传入的数组只有一个节点，直接返回即可     if(lists.length==1){return lists[0];}     //数组为空直接返回null     if(lists.length==0){return null;}     //如果长度为二，调用Merge方法，将两个链表进行排序     //注意的一点，这里数组中的每一个元素都是一个链表的头结点，     //并不是单一的一个节点     if(lists.length==2){return Merge(lists[0],lists[1]);}     ListNode[]node1=new ListNode[lists.length/2];     ListNode[]node2=new ListNode[lists.length-lists.length/2];     int index=0;     //这里将传入的数组，分割成两个数组，使用的是归并排序的思想     for(;index<node1.length;index++){node1[index]=lists[index];}     for(;index<lists.length;index++){node2[index-node1.length]=lists[index];}     ListNode node1_copy=mergeKLists(node1);     ListNode node2_copy=mergeKLists(node2);     //别忘了进行合并     return Merge(node1_copy,node2_copy);     }     //merge方法很常规，将两个有序链表合并成一盒链表     public ListNode Merge(ListNode node1,ListNode node2){         if(node1==null){return node2;}         if(node2==null){return node1;}         ListNode node=new ListNode(0);         ListNode node_temp=node;         if(node1.val<node2.val){             node.next=node1;             node=node1;             node1=node1.next;         }else{             node.next=node2;             node=node2;             node2=node2.next;         }         while(node1!=null&&node2!=null){             if(node1.val<node2.val){             node.next=node1;             node=node1;             node1=node1.next;         }else{             node.next=node2;             node=node2;             node2=node2.next;         }         }         while(node1!=null){             node.next=node1;             node=node1;             node1=node1.next;         }         while(node2!=null){             node.next=node2;             node=node2;             node2=node2.next;         }         return node_temp.next;     } }