题目来源：

23. 合并 K 个升序链表 - 力扣（LeetCode）

代码1（暴力）

/**
 * 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 mergeKLists(ListNode[] lists) {
        int k = lists.length;
        if(k==0) return null;
        if(k==1) return lists[0];

        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;

        ListNode head1 = lists[0];

        for(int i = 1; i < k; i ++) {
            ListNode head2 = lists[i];

            while(head2 != null && head1 != null) {
                if(head1.val <= head2.val) {
                    curr.next = head1;
                    head1 = head1.next;
                } else {
                    curr.next = head2;
                    head2 = head2.next;
                }
                curr = curr.next;
            }
            curr.next = head1==null?head2:head1;

            head1 = dummy.next;
            curr = dummy;
        }

        return dummy.next;
    }
}

代码分析

1.创建一个有头结点的链表做合并后链表

2.链表1和链表2进行合并，合并后将链表1更新为合并后链表，继续合并。

总的来说就是两两合并。

代码2（分治法）

/**
 * 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 mergeKLists(ListNode[] lists) {
        int k = lists.length;
        if(k == 0) return null;
        return mergeDivide(lists, 0, k - 1);
    }

    private ListNode mergeDivide(ListNode[] lists, int left, int right) {
        if(left == right) return lists[left];
        // 中点
        int mid = left + (right-left)/2;
        // 归并排序左右子链表集
        ListNode mergeLeft = mergeDivide(lists, left, mid);
        ListNode mergeRight = mergeDivide(lists, mid+1, right);
        // 合并
        return mergeTwo(mergeLeft, mergeRight);
    }

    private ListNode mergeTwo(ListNode left, ListNode right) {
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;

        while(left!=null && right!=null) {
            if(left.val <= right.val) {
                curr.next = left;
                left = left.next;
            } else {
                curr.next = right;
                right = right.next;
            }
            curr = curr.next;
        }

        curr.next = left==null?right:left;

        return dummy.next;
    }
}

代码分析

其实就是跟上一个文章的归并排序一样。只是把合并元素，从一个结点变成了一个链表。

力扣148排序链表（java)归并排序-CSDN博客