题目描述

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

示例:

输入:
[
  1->4->5,
  1->3->4,
  2->6
]
输出: 1->1->2->3->4->4->5->6

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

解法1

题目要求合并K个有序链表, 我们不妨先考虑合并两个有序链表. 为了便于操作, 我们创建一个头节点head, 该节点的value字段没有意义. 待合并的两个链表分别记为l1与l2, 为了保持合并后的链表仍然有序, 我们每次都从l1与l2中挑选当前最小的节点, 然后将其插入到头节点head.

现有链表l1, l2, 头节点head

p = head

if (l1.val < l2.val) { // 选取l1, l2当前最小的节点

p.next = l1;

l1 = l1.next;

} else {

p.next = l2;

l2 = l2.next;

}

p = p.next;

添加一个节点到存放结果的有序链表head中

上述代码片段仅仅完成了从l1或l2中取一个节点合并到有序链表head中, 我们需要加一个循环, 用尽l1或l2链表中任意一个. 因为l1与l2链表可能不等长, 即使他们等长也不一定被同时用尽. 例如l1=1->1->1->1, l2=2->2. 那么l1一定是先于l2被用尽. 因此, 当他们任意一个被用尽, 我们应当将未被用尽的链表接到head链表后(下面代码的18,20行所示). 下面的代码片段实现了将两个有序链表合并, 并返回被合并的有序链表的第一个节点.

private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(0);
        ListNode p = head;

        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                p.next = l1;
                l1 = l1.next;

            } else {
                p.next = l2;
                l2 = l2.next;
            }
            p = p.next;
        }

        if (l1 != null)
            p.next = l1;
        else
            p.next = l2;

        return head.next;
    }

题目要求将K个有序链表合并, 我们可以将K个链表先取两个合并, 被合并的链表记为tmp. 那么, K个链表还剩下K-2个链表待被合并, 我们依次将他们合并到tmp中. 计作tmp = mergeTwoLists(tmp, lists[i]), 2<=i<|lists|. 最后, 我们需要注意几个特例, 一个是待被合并的链表lists为空, 那么我们直接返回空链表. 如果待被合并的链表lists中只有一个链表, 我们直接返回那一个链表即可. 全部代码如下.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(0);
        ListNode p = head;

        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                p.next = l1;
                l1 = l1.next;

            } else {
                p.next = l2;
                l2 = l2.next;
            }
            p = p.next;
        }

        if (l1 != null)
            p.next = l1;
        else
            p.next = l2;

        return head.next;
    }

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

        ListNode tmp = mergeTwoLists(lists[0], lists[1]);

        for (int i = 2; i < lists.length; i++) {
            tmp = mergeTwoLists(tmp, lists[i]);
        }

        return tmp;
    }
}