合并K个升序链表

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

  • 示例 1：

    输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]

    解释：链表数组如下：

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

    将它们合并到一个有序链表中得到。
    1->1->2->3->4->4->5->6

  • 示例 2：

    输入：lists = []
输出：[]

  • 示例 3：

    输入：lists = [[]]
输出：[]

提示：

  • k == lists.length
  • 0 <= k <= 10^4
  • 0 <= lists[i].length <= 500
  • -10^4 <= lists[i][j] <= 10^4
  • lists[i] 按 升序 排列
  • lists[i].length 的总和不超过 10^4

Solution

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <iostream>
#include <vector>
using namespace std;

/**
 * Definition for singly-linked list.
 */
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode *mlists = new ListNode(0);
        if (lists.size() == 0) {
            return mlists->next;
        }
        if (lists.size() == 1) {
            return lists[0];
        }
        ListNode *active = mlists;
        while (1) {
            int index = 0;
            while (index < lists.size() && lists[index] == nullptr) {
                index++;
            }
            if (index > lists.size() - 1) {
                break;
            }
            for (int i = index + 1; i < lists.size(); ++i) {
                if (lists[i] != nullptr && lists[i]->val < lists[index]->val) {
                    index = i;
                }
            }
            active->next = lists[index];
            active = active->next;
            lists[index] = lists[index]->next;   
        }
        return mlists->next;
    }
};

int main() {
    vector<ListNode *> inputs;

    ListNode *temp;
    ListNode *list = new ListNode(0); // 1,1,2,3,4,4,5,6
    vector<int> input = {1, 4, 5};
    temp = list;
    for (int i = 0; i < input.size(); ++i) {
        temp->next = new ListNode(input.at(i));
        temp = temp->next;
    } 
    inputs.push_back(list->next);

    input = {1, 3, 4};
    list = new ListNode(0);
    temp = list;
    for (int i = 0; i < input.size(); ++i) {
        temp->next = new ListNode(input.at(i));
        temp = temp->next;
    } 
    inputs.push_back(list->next);

    input = {2, 6};
    list = new ListNode(0);
    temp = list;
    for (int i = 0; i < input.size(); ++i) {
        temp->next = new ListNode(input.at(i));
        temp = temp->next;
    } 
    inputs.push_back(list->next);

    ListNode *results = Solution().mergeKLists(inputs);
    while (results != nullptr) {
        std::cout << results->val << " ";
        results = results->next;
    }

    ListNode *a = nullptr;
    inputs = {a, a};
    results = Solution().mergeKLists(inputs);
    std::cout << std::endl << results;
}