LeetCode 23 : 合并K个升序链表

题目：

解题思路：
1.将多个链表合并为两个链表
2.使用21题用的，将两个有序链表合并

代码示例：

package com.zy.leetcode.LeetCode_23;

/**
 * @Author: zy
 * @Date: 2024-12-26-21:37
 * @Description: 合并K个升序链表
 * 多路递归
 */
public class ListNode_23 {

    private int val;

    private ListNode_23 next;

    public ListNode_23(int val, ListNode_23 next) {
        this.val = val;
        this.next = next;
    }

    public ListNode_23() {
    }

    public ListNode_23(int val) {
        this.val = val;
    }

    // 链表打印
    private void print(ListNode_23 node) {
        while (node != null) {
            System.out.print(node.val + " -> ");
            node = node.next;
        }
    }

    /**
     * 合并两个有序链表
     *
     * @param p1
     * @param p2
     * @return
     */
    private static ListNode_23 mergeList3(ListNode_23 p1, ListNode_23 p2) {
        // 特殊情况快速返回
        if (p1 == null) {
            return p2;
        }
        if (p2 == null) {
            return p1;
        }

        if (p1.val <= p2.val) {
            p1.next = mergeList3(p1.next, p2);
            return p1;
        } else {
            p2.next = mergeList3(p1, p2.next);
            return p2;
        }
    }

    /**
     * 返回后生成的链表
     *
     * @param lists 初始链表集合
     * @param i     左边界
     * @param j     右边界
     * @return
     */
    private static ListNode_23 spiltList(ListNode_23[] lists, int i, int j) {
        //数组内只有一个链表
        if (i == j) {
            return lists[i];
        }

        int m = (i + j) >>> 1;
        ListNode_23 left = spiltList(lists, i, m);
        ListNode_23 right = spiltList(lists, m + 1, j);
        return mergeList3(left, right);
    }

    //传入一个数组，初始化链表
    public static ListNode_23 initListNode(int[] arr) {
        ListNode_23 dummy = new ListNode_23(0);
        ListNode_23 cur = dummy;
        for (int num : arr) {
            cur.next = new ListNode_23(num);
            cur = cur.next;
        }
        return dummy.next;
    }

    /**
     * 初始化方法，传入多个数组生成链表
     */
    public static ListNode_23[] initLists(int[][] arrays) {
        ListNode_23[] lists = new ListNode_23[arrays.length];
        for (int i = 0; i < arrays.length; i++) {
            lists[i] = initListNode(arrays[i]);
        }
        return lists;
    }

    private static ListNode_23 mergeKLists(ListNode_23[] lists) {
        if (lists.length == 0) {
            return null;
        }
        return spiltList(lists, 0, lists.length - 1);
    }

    public static void main(String[] args) {
        int[][] arrays = {{1, 4, 5}, {1, 3, 4}, {2, 6}};
        ListNode_23[] lists = initLists(arrays);
        ListNode_23 result = mergeKLists(lists);
        result.print(result);
    }

}