LeetCode - 合并K个排序列表

晓痴

发布于 2019-07-24 11:55:58

5110

发布于 2019-07-24 11:55:58

文章被收录于专栏：曌的晓痴

这题是LeetCode的第23题，同样是难度为困难的题目（写文章时才发现，当时毫无察觉），一月以前完成的这道题目，这题很容易让我想到合并两个排序列表。

原题地址： https://leetcode-cn.com/problems/merge-k-sorted-lists/

题目描述：

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

输入:

[

1->4->5,

1->3->4,

2->6

]

输出: 1->1->2->3->4->4->5->6

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/merge-k-sorted-lists

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路：

这题特别容易让人想到合并两个排序列表，所以我也是基于这个思路去做的（再次基于递归）：

设定递归的结束条件，当K等于0，1或者2时，这个时候结束递归
新建一个数组，用于存放合并之后的列表，需要注意数组大小根据当前k的奇偶性去做是否+1的判断
遍历当前需要合并的list，然后两两合并
1. 在合并时，针对两个list，分别设定两个指针
2. 不停的移动指针，保证两个list中当前最小的值存放入合并之后的列表中。

中文官网题解：

https://leetcode-cn.com/problems/merge-k-sorted-lists/solution/

个人题解：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        if (lists.length == 1) {
            return lists[0];
        }
        if (lists.length == 2) {
            return merge(lists[0], lists[1]);
        }
        ListNode[] nodes;
        if (lists.length % 2 == 0) {
            nodes = new ListNode[lists.length / 2];
        } else {
            nodes = new ListNode[lists.length / 2 + 1];
        }
        int j = 0;
        for (int i = 0; i < lists.length; i += 2) {
            if (i == lists.length - 1) {
                nodes[j++] = merge(lists[i], null);
            } else {
                nodes[j++] = merge(lists[i], lists[i + 1]);
            }
        }
        return mergeKLists(nodes);
    }

    private ListNode merge(ListNode ln1, ListNode ln2) {
        if (ln1 == null) {
            return ln2;
        }
        if (ln2 == null) {
            return ln1;
        }
        ListNode head;
        if (ln1.val > ln2.val) {
            head = new ListNode(ln2.val);
            ln2 = ln2.next;
        } else {
            head = new ListNode(ln1.val);
            ln1 = ln1.next;
        }
        ListNode node = head;
        while (ln1 != null && ln2 != null) {
            if (ln1.val > ln2.val) {
                node.next = new ListNode(ln2.val);
                ln2 = ln2.next;
            } else {
                node.next = new ListNode(ln1.val);
                ln1 = ln1.next;
            }
            node = node.next;
        }
        if (ln1 == null) {
            node.next = ln2;
        } else {
            node.next = ln1;
        }
        return head;
    }
}

结果：

这也是一次不错的结果，超过了99.19%的提交记录，估计100%的只有上一题了....