题目描述

解题思路

在开始合并K个升序链表之前，我们应该先思考如何合并2个升序链表，可以参考：https://blog.csdn.net/weixin_43598687/article/details/119508065
在清楚两个升序链表的合并之后，我们可以通过以下思路实现K个升序链表的合并

• 先将lists[0]和lists[1]合并，得到新链表res;
• 再将res与lists[2]合并，得到新的res；
• 依次类推，直到与lists[K-1]合并，得到最终K个升序链表的合并结果。

代码实现

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    //合并两个升序排列的链表
    public ListNode mergeTwoLists(ListNode A, ListNode B){
        ListNode res = new ListNode(0);
        ListNode temp = res;
        while(A != null || B != null){
            if(A == null){
                res.next = B;
                break;
            }if(B == null){
                res.next = A;
                break;
            }
            if(A.val > B.val){
                res.next = B;
                B = B.next;
            }else{
                res.next = A;
                A = A.next;
            }
            res = res.next;
        }
        return temp.next;
    }
    
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists.length == 0) return null;
        ListNode res = lists[0];
        for(int i=1;i<lists.length;i++){
            res = mergeTwoLists(res, lists[i]);        //依次两两合并
        }

        return res;
    }
}