C++ 合并K个升序链表_合并k个升序链表 c++

C++ 合并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
1
2
3
4
5
6
7
8
9
10

示例2

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

示例3

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

提示：

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

思路/解法

方式一

将题目进行拆分，关键点在于如何合并两个有序链表。合并两个有序链表只需要简单迭代遍历即可。

/**
 * 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* mergeTwoLists(ListNode* list1, ListNode* list2) 
    {
        ListNode*  head     = nullptr;
        ListNode*  curNode  = nullptr;
        ListNode** temp     = nullptr;
        bool       isFirst  = true;

        while(list1 != nullptr && list2 != nullptr)
        {
            temp = (list1->val < list2->val)? &list1:&list2;        //这里务必使用二级指针，因为temp如果是一级指针，那么temp = temp->next;是无法改变list1和list2的值的，而二级指针可以间接改变list1和list2的地址。
            if(isFirst)
            {
                head    = *temp;
                curNode = *temp;
                isFirst = false;
            }
            else
            {
                curNode->next = *temp;
                curNode       = curNode->next;
            }

            *temp = (*temp)->next;
        }

        if(nullptr != list1)
        {
            if(isFirst)                                     //有一方链表为空
            {
                head = list1;
            }
            else                                            //剩下结点直接补齐
            {
                curNode->next = list1;
            }
        }

        if(nullptr != list2)
        {
            if(isFirst)
            {
                head = list2;
            }
            else
            {
                curNode->next = list2;
            }
        }

        return head;
    }


    ListNode* mergeKLists(vector<ListNode*>& lists) 
    {
        ListNode* head = nullptr;
        for(int i = 0;i < lists.size();i++)
        {
            head = mergeTwoLists(head, lists[i]);
        }

        return head;
    }
};
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

方式二

分治递归，将所有升序链表分治管理，分治组合后合并为一个升序链表。

/**
 * 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* mergeTwoLists(ListNode* list1, ListNode* list2) 
    {
        ListNode*  head     = nullptr;
        ListNode*  curNode  = nullptr;
        ListNode** temp     = nullptr;
        bool       isFirst  = true;

        while(list1 != nullptr && list2 != nullptr)
        {
            temp = (list1->val < list2->val)? &list1:&list2;        //这里务必使用二级指针，因为temp如果是一级指针，那么temp = temp->next;是无法改变list1和list2的值的，而二级指针可以间接改变list1和list2的地址。
            if(isFirst)
            {
                head    = *temp;
                curNode = *temp;
                isFirst = false;
            }
            else
            {
                curNode->next = *temp;
                curNode       = curNode->next;
            }

            *temp = (*temp)->next;
        }

        if(nullptr != list1)
        {
            if(isFirst)                                     //有一方链表为空
            {
                head = list1;
            }
            else                                            //剩下结点直接补齐
            {
                curNode->next = list1;
            }
        }

        if(nullptr != list2)
        {
            if(isFirst)
            {
                head = list2;
            }
            else
            {
                curNode->next = list2;
            }
        }

        return head;
    }

    //递归分治
    ListNode* TwoLists(vector<ListNode*>& lists, int l, int r)
    {
        if(l == r)
        {
            return lists[l];
        }

        if(l > r)
        {
            return nullptr;
        }

        int       mid = l + (r - l)/2;
        ListNode* l1  = TwoLists(lists, l,       mid);   //任意两个链表之一
        ListNode* l2  = TwoLists(lists, mid + 1, r);     //任意两个链表之一

        return mergeTwoLists(l1, l2);
    }


    ListNode* mergeKLists(vector<ListNode*>& lists) 
    {
        return TwoLists(lists, 0, lists.size() - 1);
    }
};
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