Leetcode 23. 合并K个排序链表_leetcode 23:合并 k 个排序链表

1、问题分析

题目链接：https://leetcode-cn.com/problems/merge-k-sorted-lists/
  将链表两两合并即可。代码我已经进行了详细的注释，理解应该没有问题，读者可以作为参考，如果看不懂(可以多看几遍)，欢迎留言哦！我看到会解答一下。

2、问题解决

  笔者以C++方式解决。

#include "iostream"

using namespace std;

#include "algorithm"
#include "vector"
#include "queue"
#include "set"
#include "map"
#include "string"
#include "stack"

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

struct ListNode {
    int val;
    ListNode *next;

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

class Solution {
public:
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        // 链表为空直接返回空值
        if (lists.empty()) {
            return NULL;
        }
        // 只有一个链表，直接返回该链表即可
        if (lists.size() == 1) {
            return lists[0];
        }

        // 两种合并方法，从第一个链表依次和后面的链表合并，较慢，但是简单
        //ListNode *temp = lists[0];
        //for (int i = 1; i < lists.size(); ++i) {
        //    temp = merge2Lists(temp, lists[i]);
        //}

        // 二分合并
        mergeChen(lists);
        //return temp;
        return lists[0];
    }

    /**
     * 二分法将 lists 中的链表两两合并，最后的结果保存在 lists[0]
     * @param lists
     */
    void mergeChen(vector<ListNode *> &lists) {
        // 定义左右边界
        int left = 0, right = lists.size();
        while (left < right) {
            // 定义中间节点
            int mid = (left + right) / 2;
            // 处理递推边界
            if (right == 2) {
                for (int i = 0; i < mid; ++i) {
                    // 将链表两两合并，并保存在 index 索引较低的数组中
                    lists[i] = merge2Lists(lists[i], lists[right - i - 1]);
                }
                return;
            }
            // 将链表两两合并，并保存在 index 索引较低的数组中
            for (int i = 0; i < mid; ++i) {
                lists[i] = merge2Lists(lists[i], lists[right - i - 1]);
            }
            // 这里要区分数组边界是奇数还是偶数的情况
            // 要深入理解读者可以 debug
            if (right % 2 == 0) {
                right = mid;
            } else {
                right = mid + 1;
            }


        }
    }

    /**
     * 将 listA 链表和 listB链表合并
     * @param listA
     * @param listB
     * @return
     */
    ListNode *merge2Lists(ListNode *listA, ListNode *listB) {
        // 只有一个链表有值，则直接返回另一个链表
        if (listA == NULL) {
            return listB;
        }
        // 只有一个链表有值，则直接返回另一个链表
        if (listB == NULL) {
            return listA;
        }

        // 定义新链表的头结点
        ListNode *resultTwo;
        // 头结点特殊处理，谁小，新节点的头结点就是那个
        // 同时将相应的链表向后移动一步
        if (listA->val <= listB->val) {
            resultTwo = listA;
            listA = listA->next;
        } else {
            resultTwo = listB;
            listB = listB->next;
        }
        // 结果头结点就不要操作了，定义一个临时变量去处理即可
        ListNode *headChen = resultTwo;
        // 两个链表都不为空
        while (listA != NULL && listB != NULL) {
            // 谁小，新节点就是哪个
            // 同时将相应的链表向后移动一步
            if (listA->val <= listB->val) {
                headChen->next = listA;
                headChen = listA;
                listA = listA->next;
            } else {
                headChen->next = listB;
                headChen = listB;
                listB = listB->next;
            }
        }

        // 还有链表没有处理完，则直接链接到新链表后面
        if (listA != NULL) {
            headChen->next = listA;
        }
        if (listB != NULL) {
            headChen->next = listB;
        }

        // 返回新链表的头结点
        return resultTwo;
    }
};

int main() {

    ListNode *pNode11 = new ListNode(1);
    ListNode *pNode14 = new ListNode(4);
    ListNode *pNode15 = new ListNode(5);

    pNode11->next = pNode14;
    pNode14->next = pNode15;

    ListNode *pNode21 = new ListNode(1);
    ListNode *pNode23 = new ListNode(3);
    ListNode *pNode24 = new ListNode(4);

    pNode21->next = pNode23;
    pNode23->next = pNode24;

    ListNode *pNode32 = new ListNode(2);
    ListNode *pNode36 = new ListNode(6);
    pNode32->next = pNode36;

    ListNode *pNode47 = new ListNode(7);
    ListNode *pNode48 = new ListNode(8);
    pNode47->next = pNode48;

    ListNode *pNode59 = new ListNode(9);
    ListNode *pNode510 = new ListNode(10);
    pNode59->next = pNode510;

    vector<ListNode *> lists;

    lists.push_back(pNode11);
    lists.push_back(pNode21);
    lists.push_back(pNode32);
    lists.push_back(pNode47);
    lists.push_back(pNode59);

    Solution *pSolution = new Solution;
    ListNode *pNode = pSolution->mergeKLists(lists);
    while (pNode != NULL) {
        cout << pNode->val << " ";
        pNode = pNode->next;
    }
    cout << endl;
    system("pause");
    return 0;
}
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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189

运行结果

有点菜，有时间再优化一下。

3、总结

  难得有时间刷一波LeetCode, 这次做一个系统的记录，等以后复习的时候可以有章可循，同时也期待各位读者给出的建议。算法真的是一个照妖镜，原来感觉自己也还行吧，但是算法分分钟教你做人。前人栽树，后人乘凉。在学习算法的过程中，看了前辈的成果，受益匪浅。
感谢各位前辈的辛勤付出，让我们少走了很多的弯路！
哪怕只有一个人从我的博客受益，我也知足了。
点个赞再走呗！欢迎留言哦！