leetcode23——合并K个排序链表——java实现

题目要求：

分析：

看到这道题目的时候，马上就想到了21题：将2个有序链表排序的题目。21题就是这道题的特殊情况。那我们就可以考虑将21题进行“废物利用”，即直接调用21题的方法来解决这个问题。

我们可以采用分而治之的思想，即将K个链表两两对比，排好序，然后再进一步进行两两对比。具体思想可以参照“快速排序”。

1. 首先，我们用设置left和right两个指针，分别指向存储所有链表的数组的头和尾；
2. 利用left和right，我们可以求出指向中间的middle；
3. 调用21题中的方法将left指向的链表和middle指向的链表进行合并排序，将middle + 1指向的链表和right指向的链表进行合并排序。这个过程需要进行递归；
4. 在大体上，最终要做的事情就是将最后两个有序链表进行排序，所以最终是要调用一个mergeTwoList方法，就是我们的“废物利用”的方法。

具体代码如下：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists == null) {
            return null;
        }
        return mergeK(lists, 0, lists.length - 1);
    }
    
    private ListNode mergeK(ListNode[] lists, int left, int right) {
        if(left < right) {
            int middle = (left + right) / 2;
            ListNode leftList = mergeK(lists, left, middle);
            ListNode rightList = mergeK(lists, middle + 1, right);
            return mergeTwoLists(leftList, rightList);
        } else if(left == right) {
            return lists[left];
        }
        return null;
    }
    
    private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode node = dummy;
        
        if(l1 == null) {
            return l2;
        } else if(l2 == null) {
            return l1;
        } else if(l1 == null && l2 == null) {
            return null;
        }
        
        while(l1 != null && l2 != null) {
            if(l1.val > l2.val) {
                node.next = l2;
                node = l2;
                l2 = node.next;
            } else {
                node.next = l1;
                node = l1;
                l1 = node.next;
            }
        }
        
        if(l1 != null)
            node.next = l1;
        if(l2 != null)
            node.next = l2;
        
        return dummy.next;
    }
}