【链表】Leetcode 23. 合并 K 个升序链表【困难】

合并 K 个升序链表

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

解题思路

合并多个有序链表可以使用归并排序的思想

• 使用分治法，将链表数组分为两半。
• 递归地合并左半部分和右半部分。
• 合并两个有序链表的方法，即使用合并两个有序链表的算法。

Java实现

public class MergeKSortedLists {

    static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }

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

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

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

        return mergeTwoLists(leftList, rightList);
    }

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }

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

    public static void main(String[] args) {
        // 构造链表数组
        ListNode[] lists = new ListNode[3];
        lists[0] = new ListNode(1);
        lists[0].next = new ListNode(4);
        lists[0].next.next = new ListNode(5);

        lists[1] = new ListNode(1);
        lists[1].next = new ListNode(3);
        lists[1].next.next = new ListNode(4);

        lists[2] = new ListNode(2);
        lists[2].next = new ListNode(6);

        // 调用 mergeKLists 方法合并链表数组
        MergeKSortedLists solution = new MergeKSortedLists();
        ListNode result = solution.mergeKLists(lists);

        // 打印合并后的链表
        while (result != null) {
            System.out.print(result.val + " ");
            result = result.next;
        }
        // 输出：1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6
    }
}

时间空间复杂度

• 时间复杂度：O(nlogk)，其中 n 是所有链表中的节点总数，k 是链表的个数，每一层合并的时间复杂度为 O(n)，总共有 O(logk) 层。
• 空间复杂度：O(log(K) + n)，其中 log(K) 是递归深度，n 是链表的长度。