题目

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

示例:

输入:

1
2
3
4
5

[
  1->4->5,
  1->3->4,
  2->6
]

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

暴力循环

每次找到当前列中最小值，加入到结果链表中，将此值替换为其后继。时间复杂度Nk。 （N为所有链表中的元素个数总和）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution {
public:
    int findMin(vector<ListNode*> &lists) {
        int min = INT_MAX;
        int pos = -1;
        for (int i = 0; i < lists.size(); i++) {
            if (lists[i] && lists[i]->val < min) {
                min = lists[i]->val;
                pos = i;
            }
        }
        return pos;
    }

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode dummy(0);
        ListNode *curr = &dummy;

        while(true) {
            int pos = findMin(lists);
            if (pos == -1)
                break;
            curr->next = lists[pos];
            curr = lists[pos];
            lists[pos] = lists[pos]->next;
        }

        return dummy.next;
    }
};

改进1: 递归合并

类似 MergeSort，两两递归合并。时间复杂度Nlog(k)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

class Solution {
public:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        ListNode dummy(0);
        ListNode *curr = &dummy;
        while (l1 && l2) {
            if (l1->val < l2->val) {
                curr->next = l1;
                curr = l1;
                l1 = l1->next;
            } else {
                curr->next = l2;
                curr = l2;
                l2 = l2->next;
            }
        }
        if (l1)
            curr->next = l1;
        if (l2)
            curr->next = l2;

        return dummy.next;
    }
    
    ListNode *merge(vector<ListNode*>& lists, int start, int end) {
        if (start > end) return nullptr;
        if (start == end) return lists[start];
        
        int mid = (start + end) / 2;
        ListNode *left = merge(lists, start, mid);
        ListNode *right = merge(lists, mid+1, end);        
        return mergeTwoLists(left, right);
    }

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return merge(lists, 0, lists.size()-1);
    }
};

改进2：优先级队列

构造一个规模为 k 的优先级队列（最小堆），初始将各链表头元素入队，每次出队一个元 素，并将其后继入队。时间复杂度Nlog(k)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution{
public:
    struct compareFunc {
        bool operator()(ListNode* node1, ListNode* node2) {
            return node1->val > node2->val;
        }
    };

    ListNode* mergeKLists2(vector<ListNode*>& lists) {
        priority_queue<ListNode*, vector<ListNode*>, compareFunc> pq;

        for (ListNode* node : lists) {
            if (node != nullptr)
                pq.push(node);
        }

        ListNode dummy = ListNode(0);
        ListNode *current = &dummy;

        while (!pq.empty()) {
            current->next = pq.top();
            pq.pop();
            current = current->next;
            if (current->next != nullptr)
                pq.push(current->next);
        }

        return dummy.next;
    }
};