牛客刷题系列（C++）——详解MGJ8 链表合并（目前内存开销最小）

题目

这是一道很简单的合并两个有序链表的题目

思路

我的思路是先创建两个链表 list1 和 list2 ，用于存储输入数据

再创建第三个链表 list3 用于保存合并之后的链表

注意：

这里给的测试数据是两个链表长度相同

所以很容易的就忽略了两个链表长度不相同的测试数据

1. 如果 list1 长度大于 list2
   那么当list2遍历结束时，应该把list1剩下部分的数据直接放入list3中

2. 如果 list1 长度小于 list2
   那么当list1遍历结束时，应该把list2剩下部分的数据直接放入list3中

以上两种情况都需要注意在传递到list3中，其指针得指向情况

代码

这部分直接上代码，写上详细的注释

#include 
#include 

using namespace std;

int main()
{
    list <int> list1,list2,list3;		/// 创建三个链表。缺点比较占用内存
    int temp;							/// 临时变量，用于保存每次输入链表的数据
    while(cin >> temp)					/// 每次循环输入。不建议使用scanf()!=EOF，每一行输入结束还需要加上ctrl z
    {
        list1.push_back(temp);			/// 第一行输入进入链表
        if(getchar() == '\n')			/// 判断是否输入结束
            break;
    }
    while(cin >> temp)
    {
        list2.push_back(temp);
        if(getchar() == '\n')
            break;
    }

    list<int>::iterator li1 = list1.begin();	/// 创建list1的容器（理解为指针li1）
    list<int>:: iterator li2 = list2.begin();	// 创建list2的容器

    for(int i=0;i < list1.size()+list2.size();i++)	/// 循环两个链表的长度来进行合并
    {
        if(li1==list1.end())					/// 判断list1是否遍历完成（可以理解为list1比list2短）
        {
            list3.push_back(*li2);				/// 直接把list2剩余部分添加到list3中
            li2++;								/// list2的指针指向下一个节点
            continue;
        }
        if(li2 == list2.end())					/// 判断list2是否遍历完成（可以理解为list1比list2长）
        {
            list3.push_back(*li1);				/// 直接把list1剩余部分添加到list3中
            li1++;								/// list1的指针指向下一个节点
            continue;
        }

        if(*li1 <= *li2)						/// 比较当前两个链表指针下哪个数据小就选择小的放入list3中
        {
            list3.push_back(*li1);
            li1++;								/// list1的指针指向下一个节点
        }

        else
        {
            list3.push_back(*li2);
            li2++;								/// list2的指针指向下一个节点
        }
    }

    int i=0;
    for(list<int> ::iterator li3 = list3.begin();li3 != list3.end();li3++)	/// 创建容器li3循环遍历list3并输出
    {
        if(i++)
            printf(" ");
        printf("%d",*li3);
    }

    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

结果

程序输出结果没有问题

最后还得到了一个比较低的开销

当前题目下内存开销是最少的