leetcode-023

题目

Merge k Sorted Lists

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

Example:

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

分析

这道题的描述十分简单，要求也清晰，就是要我们把k个有序的链表合并成一个有序的链表，我们熟悉的应该是合并两个链表，但这里链表数目增加了，算法的设计就自然变难了。

合并两个有序链表

我们先回顾经典的合并两个链表的问题，最好的方法如下：

1. 从合并两个链表头节点开始，比较两个链表头节点值的大小，若list的头节点值更小，则把result_list的头指针指向这个节点，并把list的头节点往后移一次
2. 循环判断剩余节点：继续比较两个链表头节点大小，若list的头节点值更小，则把result_list尾节点的next指针指向list的头节点，并把list的头节点往后移一次。推出循环的条件是两个链表中有一个头节点指针为空
3. 使result_list的尾节点的next指针指向不为空的那个链表的头节点

代码如下：

//list1和list2分别指向要合并的两个有序链表的头节点
    ListNode* merge(ListNode* list1, ListNode* list2) {
        if (list1 == NULL) return list2;
        else if (list2 == NULL) return list1;
        ListNode* head = NULL;
        if (list1->val < list2->val) {
            head = list1;
            list1 = list1->next;
        }
        else {
            head = list2;
            list2 = list2->next;
        }
        ListNode* tmp = head;
        while (list1 != NULL && list2 != NULL) {
            if (list1->val < list2->val) {
                head->next = list1;
                list1 = list1->next;
            }
            else {
                head->next = list2;
                list2 = list2->next;
            }
            head = head->next;
        }
        if (list1 == NULL) head->next = list2;
        else head->next = list1;
        return tmp;
    }

这种方法的时间复杂度最大为O(n)，而空间复杂度为O(1)，效率挺不错了。

合并k个有序链表

有了前面的基础后再回到这个题目，很容易会想采用同样的方法：比较这k个链表的头节点的值，然后把最小的那个头节点作为合并后链表的头节点，再不断循环。但这样的话每得到一个正确位置的节点就要循环一次，开销太大了，不适用于此种情况。

鉴于最近课上一直在讲分治算法，很自然地我就想到了用分治法来解决这个问题。既然一次性合并k个链表是困难的，而一次性合并两个链表是容易的，那使用分治法来把这个大问题(合并k个)分成很多个小问题(合并2个)，再一一解决，就很容易了。

解法

按照前面的思路，解决方法可以分为以下几个步骤：

1. 使用二分法把这k个链表不断递归分成两个子部分，最终得到的子部分所含有的链表数全为1，这是最底层
2. 最底层不需要合并，因为一个链表的合并自然就是它本身
3. 向上递归，倒数第二层的合并全是两个有序链表的合并，这在之前已经得到解决，合并之后链表数减半，再继续递归合并，一层层合并完就得到了最终的链表

这种方法的时间复杂度是O(Nlogk)，总共分成了logk层，而每一层中合并两个有序链表总共的时间复杂度为O(N)，因此总的就为O(Nlogk)

至于空间复杂度，我们在合并两个链表的过程中并没有额外开辟新的空间，而是仅通过改变指针的指向就实现了合并，因此为O(1)

代码

/*
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Example:
Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6
*/

#include <iostream>
#include <vector>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
private:
    //合并两个有序链表
    ListNode* merge(ListNode* list1, ListNode* list2) {
        if (list1 == NULL) return list2;
        else if (list2 == NULL) return list1;
        ListNode* head = NULL;
        if (list1->val < list2->val) {
            head = list1;
            list1 = list1->next;
        }
        else {
            head = list2;
            list2 = list2->next;
        }
        ListNode* tmp = head;
        while (list1 != NULL && list2 != NULL) {
            if (list1->val < list2->val) {
                head->next = list1;
                list1 = list1->next;
            }
            else {
                head->next = list2;
                list2 = list2->next;
            }
            head = head->next;
        }
        if (list1 == NULL) head->next = list2;
        else head->next = list1;
        return tmp;
    }
    ListNode* mergelist(vector<ListNode*>& lists, int left, int right) {
        int mid = (left + right) / 2;
        if (left < right) {
            ListNode* list1 = mergelist(lists, left, mid);
            ListNode* list2 = mergelist(lists, mid + 1, right);
            ListNode* mergedList = merge(list1, list2);
            return mergedList;
        }
        return lists[left];
    }
public:
    //思路:先采用分治法把问题分成两个子问题(不断向下递归分解)，到最后一层得到的是单独的一条链表
    //      合并两条链表为一条，向上递归继续合并
    //      思路很类似于归并排序
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.size() == 0) return NULL;
        return mergelist(lists, 0, lists.size() - 1);
    }
};

int main() {
    
}