题解 | #合并k个已排序的链表#

基本思路

合并k个排序好的链表，可以用归并排序，将链表数组逐步划分成左右两个部分，知道左右两个部分只有一个链表节点，此时就可以对这两个链表节点进行合并排序了，排序好的链表向上返回一个节点，再跟另一半排序好的链表节点合并排序，这样逐步向上合并返回，最终就得到一个合并整个链表数组的节点。

如何确定划分到只剩下一个节点呢？当划分的right大于left时，说明此时已经超过划分范围，返回一个null就行，因为合并的函数可以处理为null的链表节点，如果left跟right相等，说明此时已经数组只剩一个节点，此时可以返回给上层排序了。

参考

参考题解

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param lists ListNode类ArrayList 
     * @return ListNode类
     */
    private ListNode Merge(ListNode pHead1, ListNode pHead2) {
        if (pHead1 == null) {
            return pHead2;
        }
        if (pHead2 == null) {
            return pHead1;
        }

        ListNode head = new ListNode(-1);
        ListNode current = head;

        while(pHead1 != null && pHead2 != null) {
            if (pHead1.val < pHead2.val) {
                current.next = new ListNode(pHead1.val);  // 这里是把节点摘出来，所以不用新创建一个节点，直接current.next = pHead1;就行
                current = current.next;
                pHead1 = pHead1.next;
            }
            else {
                current.next = new ListNode(pHead2.val);
                current = current.next;
                pHead2 = pHead2.next;
            }
        }

        while(pHead1 != null) {
            current.next = new ListNode(pHead1.val);
            current = current.next;
            pHead1 = pHead1.next;
        }
        while(pHead2 != null) {
            current.next = new ListNode(pHead2.val);
            current = current.next;
            pHead2 = pHead2.next;
        }

        return head.next;
    }
    // 归并排序，将数组划分到一个一个元素以后，再两两合并成一个，返回给上层合并
    private ListNode divideMerge(ArrayList<ListNode> lists, int left, int right) {
        if (left > right) {
            return null; // 此次划分超过范围了，返回null，上一层的一个链表也是可以和null合并的，返回不为空的链表即可
        }
        if (left == right) {
            return lists.get(left);  // 此次划分只剩下一个链表元素了，返回给上层合并
        }

        int mid = (left + right) / 2;

        return Merge(divideMerge(lists, left, mid), divideMerge(lists, mid+1, right));  // 合并左右部分的元素，divideMerge会从底层返回一个排好序的链表。
    }
    public ListNode mergeKLists (ArrayList<ListNode> lists) {
        // write code here
        return divideMerge(lists, 0, lists.size()-1);
    }
}