23. Merge k Sorted Lists

发表于 | 分类于 | |

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

题意表述异常简练：合并多个有序链表

虽然题目不长，但是这道在LeetCode上却是被标记为hard的题目。

自己在做这道题的时候，受两个有序链表合并题目，用两个指针不断比较，逐步前进的影响，所以开始想用多个指针，即建一个vector 来存储跟踪每一行即将被添加的数的所有指针。

但是这样有两个问题：

  1. 每次指针所指数被添加到总列表后需要将指针往前挪一位，不如vector下标的自增方便

  2. 循坏的结束

    需要所有指针都指到最后，即都为NULL，两个还好，

    多个就不好判断了

    。转化成vector就好判断多了：

    • 在每一行的最后加入一个最大的数INF，这样这个数永远不会被加到总列表中
    • 统计原来的多个列表总共有多少个节点，即allNodes
    • 这样循环allNodes次之后必能将所有的节点加入到总列表中了

具体实现：

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
//
// Created by chaopengz on 2017/10/13.
//
#include "head.h"

/**
 * 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(nullptr) {}
};

class Solution {
public:
    ListNode *mergeKLists(vector<ListNode *> &lists)
    {
        int INF = 2147483647;
        int Min;
        vector<vector<int>> vv;
        int len = lists.size();
        ListNode *p;
        int allNodes = 0;
		//将链表转为二维vector
        for (int i = 0; i < len; ++i)
        {
            vector<int> v;
            p = lists[i];
            while (p)
            {
                v.push_back(p->val);
                p = p->next;
            }
            v.push_back(INF);
            vv.push_back(v);
            allNodes += (v.size() - 1);
        }
        //每一行即将被添加的数的索引
        vector<int> index;
        //都从0，即链表头起第一个数开始
        for (int j = 0; j < len; ++j)
        {
            index.push_back(0);
        }
        int recoderIndex;
        ListNode *res = nullptr, *pre = nullptr;
        ListNode *pNode;
        for (int k = 0; k < allNodes; ++k)
        {
            Min = INF;
            for (int i = 0; i < len; ++i)
            {
                //找出最小的值
                if (vv[i][index[i]] < Min)
                {
                    Min = vv[i][index[i]];
                    //记录最小值所在的行
                    recoderIndex = i;
                }
            }

            pNode = new ListNode(Min);
            index[recoderIndex]++;
            if (res)
            {
                pre->next = pNode;
                pre = pNode;

            } else
            {
                res = pNode;
                pre = res;
            }
        }
        return res;
    }
};

看了Discussion后，发现大佬的解法更为简单，即采取分而治之（Divide and Conquer）的思想。

两个有序链表不是很简单吗？那么多个有序的列表难道不是不断的两两合并，最后合到只剩下一个为止？

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
ListNode *mergeKLists(vector<ListNode *> &lists) {
    if(lists.empty()){
        return nullptr;
    }
    while(lists.size() > 1){
        //利用队列的思想，把第一个和第二个合并，然后新的列表加入到最后
        lists.push_back(mergeTwoLists(lists[0], lists[1]));
        //丢弃最前面两个已经被合并好了的列表
        lists.erase(lists.begin());
        lists.erase(lists.begin());
    }
    return lists.front();
}
//合并两个有序链表，递归解法，更加简洁易懂
ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
    if(l1 == nullptr){
        return l2;
    }
    if(l2 == nullptr){
        return l1;
    }
    if(l1->val <= l2->val){
        l1->next = mergeTwoLists(l1->next, l2);
        return l1;
    }
    else{
        l2->next = mergeTwoLists(l1, l2->next);
        return l2;
    }
}