题解 | #牛群的合并# java

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param lists ListNode类一维数组
     * @return ListNode类
     */
    public ListNode mergeKLists(ListNode[] lists) {
        // write code here
        if (lists == null || lists.length == 0) {
            return null;
        }

        return mergeLists(lists, 0, lists.length - 1);
    }

    private ListNode mergeLists(ListNode[] lists, int start, int end) {
        if (start == end) {
            return lists[start];
        }

        int mid = start + (end - start) / 2;
        ListNode left = mergeLists(lists, start, mid);
        ListNode right = mergeLists(lists, mid + 1, end);

        return mergeTwoLists(left, right);
    }

    private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null || l2 == null) {
            return l1 != null ? l1 : l2;
        }

        if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
}

该题考察了以下几个知识点：

链表的基本操作：链表是一种常见的数据结构，通过节点和指针将数据串联起来。在这道题目中，要合并多个有序链表，因此需要熟悉链表的基本操作，如节点的创建、插入、删除等。
分治法（Divide and Conquer）：分治法是一种问题解决方法，将大问题分解为相互独立且规模较小的子问题，然后将子问题的解合并起来得到原问题的解。在这道题目中，将多个链表分治地两两合并，最终得到合并后的链表。
递归算法：递归是一种函数自身调用自身的算法。在这道题目中，合并两个有序链表的过程可以使用递归实现，不断比较两个链表当前节点的值，将较小值的节点作为合并后的结果，并递归地继续合并剩余部分。

代码解释大纲：

首先判断输入是否合法，如果链表数组为空或长度为0，则直接返回null。
创建mergeKLists方法，参数为链表数组lists，返回合并后的链表头节点。a. 在mergeKLists方法中，调用mergeLists方法，传入链表数组、起始位置0和终止位置lists.length - 1。b. 在mergeLists方法中，判断是否只有一个链表，当start等于end时，表示只有一个链表，直接返回该链表。c. 否则，计算中间位置mid，然后递归地调用mergeLists方法将链表数组分为左右两部分进行合并。d. 最后，调用mergeTwoLists方法将左右两部分链表合并起来，并返回合并后的链表头节点。
创建mergeTwoLists方法，参数为两个有序链表的头节点l1和l2，返回合并后的链表头节点。

判断边界情况，如果其中一个链表为空，则直接返回另一个链表。
递归地比较两个链表当前节点的值，将较小值的节点作为合并后的结果。
递归调用mergeTwoLists方法，传入剩余部分的链表，将其与较小值的节点合并。
返回合并后的链表头节点。