合并K个排序链表

发表于
本文字数： 2k 阅读时长 ≈ 2 分钟

LeetCode题目，23. Merge K Sorted Lists

先看题目描述

rynYxs.png

大意就是给定一个链表数组，每个链表都已按升序排列，让我们将所有链表合并成一个升序链表

算法和思路

看到题目说给定的 K 个链表全都是按升序排列的，又看到要将链表合并，很快就联想到归并排序中将两个升序数组合并为一个升序数组的过程中，于是发现这题可以用类似归并排序的分治做法

大致思路就是每次将链表数组进行二分，然后对二分出的部分递归的合并为一个链表，递归出口是要合并的部分中只有一个链表时，直接返回该链表即可。然后就是再实现一个方法，可以将两个有序链表合并为一个有序链表，这个的做法可以参照 21.合并两个有序链表，代码如下，其中使用到了哑节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
private ListNode mergeTowSortedLists(ListNode l1, ListNode l2) {
        ListNode dump = new ListNode(-1);
        ListNode pre = dump;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                pre.next = l1;
                l1 = l1.next;
            } else {
                pre.next = l2;
                l2 = l2.next;
            }
            pre = pre.next;
        }
        pre.next = l2 == null ? l1 : l2;
        return dump.next;
    }

算法源码

这个代码基本上和归并排序的代码结构是一致的，对归并排序比较熟悉的话很快就可以写出来

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        int len = lists.length;
        if (len == 0) {
            return null;
        }
        return mergeKListsRecrusively(lists, 0, len - 1);
    }

    private ListNode mergeKListsRecrusively(ListNode[] lists, int left, int right) {
        if (left == right) {
            return lists[left];
        }
        int mid = (left + right) / 2;
        ListNode l1 = mergeKListsRecrusively(lists, left, mid);
        ListNode l2 = mergeKListsRecrusively(lists, mid + 1, right);
        return mergeTowSortedLists(l1, l2);
    }

    private ListNode mergeTowSortedLists(ListNode l1, ListNode l2) {
        ListNode dump = new ListNode(-1);
        ListNode pre = dump;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                pre.next = l1;
                l1 = l1.next;
            } else {
                pre.next = l2;
                l2 = l2.next;
            }
            pre = pre.next;
        }
        pre.next = l2 == null ? l1 : l2;
        return dump.next;
    }
}