问题描述

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

合并k个有序链表。

举个例子：

Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6

解法1

Thanks @tt2767{:target=”_blank”}

主要是使用分治思想。

来看下示意图：

将数组中的元素想象成链表即可。

注意，如果k为奇数时，最中间的元素则无法进行合并。

所以，需要这样： n = (n + 1) >> 1。

该解法的时间复杂度为O(nlog(k))，空间复杂度为O(1)

来看下实现：

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {

        if (lists == null || lists.length == 0){
            return null;
        }
        int n = lists.length;
        int i = 0, j = n - 1;

        while (n != 1){
            while (i < j){
                lists[i] = merge(lists[i], lists[j]);
                i++;
                j--;
            }
            n = (n + 1) >> 1;
            i = 0;
            j = n - 1;
        }
        return lists[0];
    }

    private ListNode merge(ListNode l1, ListNode l2){
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        while (l1 != null && l2 != null){
            if (l1.val <= l2.val){
                cur.next = l1;
                cur = l1;
                l1  = l1.next;
            } else {
                cur.next = l2;
                cur = l2;
                l2  = l2.next;
            }
        }
        if (l1 != null) cur.next = l1;
        if (l2 != null) cur.next = l2;
        return dummy.next;
    }
}

Enjoy it !