1. class Solution {
    2.     public ListNode mergeKLists(ListNode[] lists) {
    3.         if(lists == null || lists.length == 0){
    4.             return null;
    5.         }
    6.         if(lists.length == 1){
    7.             return lists[0];
    8.         }
    9.         return split(lists, 0, lists.length-1);
    10.     }
    12.     public ListNode split(ListNode[] lists, int left, int right){
    13.         if(left == right){
    14.             return lists[left];
    15.         }
    16.         int mid = left + (right-left)/2;
    18.         return mergeTwoLists(split(lists, left, mid), split(lists, mid+1, right));
    20.     }
    22.     public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    23.         if(l1 == null){
    24.             return l2;
    25.         }
    26.         if(l2 == null){
    27.             return l1;
    28.         }
    29.         ListNode head = null;
    30.         ListNode tmp = null;
    32.         if(l1.val <= l2.val){
    33.             tmp = l1;
    34.             head = l1;
    35.             l1 = l1.next;
    36.         } else {
    37.             tmp = l2;
    38.             head = l2;
    39.             l2 = l2.next;
    40.         }
    42.         while(l1!=null && l2!=null){
    43.             if(l1.val <= l2.val){
    44.                 tmp.next = l1;
    45.                 l1 = l1.next;
    46.             } else {
    47.                 tmp.next = l2;
    48.                 l2 = l2.next;
    49.             }
    50.             tmp = tmp.next;
    51.             tmp.next = null;
    52.         }
    53.         if(l1 != null){
    54.             tmp.next = l1;
    55.         }
    56.         if(l2 != null){
    57.             tmp.next = l2;
    58.         }
    59.         return head;
    60.     }
    61. }