23. 合并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

示例 2:

输入:lists = []
输出:[]

示例 3:

输入:lists = [[]]
输出:[]

**提示: **

  • k == lists.length
  • 0 <= k <= 10^4
  • 0 <= lists[i].length <= 500
  • -10^4 <= lists[i][j] <= 10^4
  • lists[i] 按 升序 排列
  • lists[i].length 的总和不超过 10^4

算法思路:

1.方法一:暴力,把链表数组中的所有链表的数拿出来放到一个 list 中,再对 list 排序,最后由 list 生成对应的链表。

2.方法二:分治法

代码实现:

方法一:暴力

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        List<Integer> res = new ArrayList<>();
        for (ListNode list : lists) {
            res.addAll(getListByNode(list));
        }
        res.sort(Comparator.comparingInt(o -> o));
        return toNode(res);
    }

    public List<Integer> getListByNode(ListNode node) {
        ListNode p = node;
        List<Integer> res = new ArrayList<>();
        while (p != null) {
            res.add(p.val);
            p = p.next;
        }
        return res;
    }

    public ListNode toNode(List<Integer> list) {
        if (list == null || list.size() == 0) return null;
        ListNode root = new ListNode(list.get(0));
        ListNode t = root;
        for (int i = 1; i < list.size(); i++) {
            ListNode p = new ListNode(list.get(i));
            t.next = p;
            t = p;
        }
        return root;
    }

}

方法二:分治法

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        return divideFn(lists);
    }

    // 分治法
    public ListNode divideFn(ListNode[] lists) {
        if (lists.length == 0) return null;
        if (lists.length == 1) return lists[0];
        if (lists.length == 2) {
            return mergeTwoLists(lists[0], lists[1]);
        }

        // 将大的数组二分拆成两个数组 l1,l2
        int mid = lists.length / 2;
        ListNode[] l1 = Arrays.copyOfRange(lists, 0, mid);
        ListNode[] l2 = Arrays.copyOfRange(lists, mid, lists.length);

        // 两个数组分别递归求其 对应的链表,再合并
        return mergeTwoLists(divideFn(l1), divideFn(l2));
    }

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

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

Q.E.D.


以无限为有限,以无法为有法