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

import java.util.*;
import java.util.stream.Collectors;
/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param lists ListNode类ArrayList
     * @return ListNode类
     */
    public ListNode mergeKLists (ArrayList<ListNode> lists) {
        if (lists.isEmpty()) {
            return null;
        }
        if (lists.size() == 1) {
            return lists.get(0);
        }
        ListNode merge = lists.get(0);
	  	// 只需要记录每次合并后的链表，然后作为下一次对比的链表即可，后面两个方法在合并有序链表已经解释过了，这里不在解释
        for (int i = 1; i < lists.size(); i++) {
            merge = merge(merge, lists.get(i));
        }
        return merge;
    }

    /**
     * 两个有序链表合并成一个有序链表
     */
    public ListNode merge(ListNode pHead1, ListNode pHead2) {
        ListNode merge = new ListNode(-1);
        ListNode dump = merge;
        merge(dump, pHead1, pHead2);
        return merge.next;
    }

    /**
     * 两个有序链表合并成一个有序链表
     */
    public ListNode merge(ListNode dump, ListNode pHead1, ListNode pHead2) {
        if (pHead1 == null) {
            dump.next = pHead2;
            return dump;
        }
        if (pHead2 == null) {
            dump.next = pHead1;
            return dump;
        }
        int val1 = pHead1.val;
        int val2 = pHead2.val;
        if (val1 <= val2) {
            ListNode next = pHead1.next;
            pHead1.next = null;
            dump.next = pHead1;
            merge(dump.next, next, pHead2);
        } else {
            ListNode next = pHead2.next;
            pHead2.next = null;
            dump.next = pHead2;
            merge(dump.next, pHead1, next);
        }
        return null;
    }
}