LeetCode 23. Merge k Sorted Lists

Problem

LeetCode 23. Merge k Sorted Lists

1. 题目简述

合并多个有序链表。例如：

Example:

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

2. 算法思路

极其经典的老题目，类似题目：LeetCode 21. Merge Two Sorted Lists

我们首先需要注意的是k个数组的话如果继续使用迭代的方式，会产生很多条件的判断，例如每次添加了一个节点之后，需要判断k个List中哪些已经到头了，计算起来很麻烦，而且易错。那么我们如何将问题分解成之前做过的“Merge 2 Sorted Arrays”呢？答案就是分治法。

分治法

每次二分整个lists，直到分为了两个list的合并或者一个单独的list，合并它们并返回。

时间复杂度:O(n * logk)，n是所有list节点总数，k是list个数。这是因为我们其实一共需要对每个元素合并logk次，每次返回上一级都要重新合并，因此是乘法。

空间复杂度:O(logk)，大部分的操作都是O(1)空间的，只有递归层数是需要压栈要空间。

//**
 * 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.length == 0) {
            return null;
        }
        if (lists.length == 1) {
            return lists[0];
        }

        return mergeLists(lists, 0, lists.length - 1);

    }

    // This function is used to divide numerous lists into smaller parts and merge them into one list.
    private ListNode mergeLists(ListNode[] lists, int start, int end) {
        if (start == end) {
            return lists[start];
        } else if (start == end - 1) {
            return mergeTwoLists(lists[start], lists[end]);
        } else {
            int mid = start + (end - start) / 2;

            ListNode left = mergeLists(lists, start, mid);
            ListNode right = mergeLists(lists, mid + 1, end);

            return mergeTwoLists(left, right);
        }
    }

    private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        ListNode head = new ListNode(0);
        ListNode ptr = head;

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

        ptr.next = l1 == null ? l2 : l1;

        return head.next;
    }
}