牛客网高频算法题系列-BM5-合并k个已排序的链表

题目形容

合并 k 个升序的链表并将后果作为一个升序的链表返回其头节点。

原题目见：BM5 合并k个已排序的链表

解法一：分治法

分治法，能够将大问题分解成小问题，而后持续分解成最小的子问题并解决之。

具体处理过程如下，将k个链表分解成2局部解决，递归解决这2局部，并调用 BM4 合并两个排序的链表 中的办法将2个合并好的链表进行合并，最小的子问题的条件是：

  • 没有待合并的链表，间接返回空。
  • 如果只有一个链表，则不须要合并，间接返回该链表。

如果不满足，则须要持续合成并递归解决。

阐明：BM4 合并两个排序的链表，请参考 牛客网高频算法题系列-BM4-合并两个排序的链表。

代码

import com.google.common.collect.Lists;import java.util.ArrayList;import java.util.List;public class Bm005 {    /**     * 分治法     *     * @param lists     * @return     */    public static ListNode mergeKLists(List<ListNode> lists) {        // 如果没有待合并的链表，间接返回空        if (lists == null || lists.size() == 0) {            return null;        }        // 如果只有一个链表，则不须要合并，间接返回该链表        if (lists.size() == 1) {            return lists.get(0);        }        int left = 0, right = lists.size();        int mid = (left + right) / 2;        // 递归调用以后办法将原有的链表汇合分成2局部别离进行合并        // 而后调用 BM4 合并两个排序的链表 中的办法将2个合并好的链表进行合并        return Bm004.merge(mergeKLists(lists.subList(0, mid)), mergeKLists(lists.subList(mid, right)));    }    public static void main(String[] args) {        ListNode listNode1 = ListNode.testCase3();        System.out.println("链表一");        ListNode.print(listNode1);        ListNode listNode2 = ListNode.testCase4();        System.out.println("链表二");        ListNode.print(listNode2);        ListNode listNode3 = new ListNode(7);        System.out.println("链表三");        ListNode.print(listNode3);        ArrayList<ListNode> lists = Lists.newArrayList(listNode1, listNode2, listNode3);        ListNode result = mergeKLists(lists);        // 测试用例，冀望输入： 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7        System.out.println("合并后的链表");        ListNode.print(result);    }}
$1.01^{365} ≈ 37.7834343329$
$0.99^{365} ≈ 0.02551796445$
置信保持的力量！