题目描述

构建一个单向链表，链表中包含一组整数数据。输出链表中的所有元素。
要求：

1. 使用自定义的链表数据结构
2. 提供一个 linkedList 类来管理链表，包含构建链表和输出链表元素的方法
3. 在 main 函数中，创建一个包含一组整数数据的链表，然后调用链表的输出方法将所有元素打印出来

输入描述

包含多组测试数据，输入直到文件尾结束。
每组的第一行包含一个整数 n，表示需要构建的链表的长度。
接下来一行包含 n 个整数，表示链表中的元素。

输出描述

每组测试数据输出占一行。
按照顺序打印出链表中的元素，每个元素后面跟一个空格。

输入示例

5
1 2 3 4 5
6
3 4 5 6 7 8

输出示例

1 2 3 4 5
3 4 5 6 7 8

题解

#include <iostream>
using namespace std;
struct ListNode
{
    int val;
    ListNode* next;
    ListNode(int x):val(x), next(nullptr){}
};
int main()
{   
    int n = 0, value = 0;
    while(cin>>n)
    {
        ListNode *head = new ListNode(0);//虚拟头节点-方便使用
        ListNode *cur = head;            //工作节点，最重要的思想
        while(n--)
        {
            cin>>value;
            cur->next = new ListNode(value);
            cur = cur->next;
        }
        cur = head;//时刻记住cur位置
        while(cur->next != nullptr)
        {
            cout<<cur->next->val<<" ";
            cur = cur->next;
        }
        cout<<endl;
    }
    return 0;
}

解题技巧

使用类/结构体构建链表，掌握操作链表的方式；熟练理解、使用new

struct ListNode//链表结构体
{
    int val;
    ListNode* next;
    ListNode(int x):val(x), next(nullptr){}
};

//链表初始化，需要head与cur指针
ListNode *head = new ListNode(0);//虚拟头节点-方便使用
ListNode *cur = head;            //工作节点，最重要的思想

//添加方式，注意头节点使用
while(n--)
{
    cin>>value;
    cur->next = new ListNode(value);
    cur = cur->next;
}
cur = head;//时刻记住cur位置
while(cur->next != nullptr)//遍历方式
{
    cout<<cur->next->val<<" ";
    cur = cur->next;
}

知识背景

前言

在之前的学习中，我们接触到了字符串和数组这两种结构，它们具有着以下的共同点

• 元素按照一定的顺序来排列
• 可以通过索引来访问数组中的元素和字符串中的字符

但是它们也都有着一些缺点：

• 固定大小：数组的大小通常是固定的，一旦分配了内存空间，就难以动态地扩展或缩小，如果需要存储的元素数量超出了数组的大小，就需要重新分配更大的数组，并将原来数组的内容复制过去，需要执行很多额外的操作。
• 内存是连续的：正是因为元素按照一定的顺序来排列，它们在计算机内存中的存储也是连续的，这也就意味着，当需要存储一些需要占用空间较大的内容，也只能找一些大块的内存区域，而空间比较小的内存区域就被浪费了，从而导致了内存资源浪费。
• 固定的数据类型：数组要求所有元素具有相同的数据类型，字符串存储的都是字符，如果需要存储不同类型的数据，数组和字符串就显得无能为力了。

还有重要的一点是，如果我们想要往数组中新增加或者删除一个元素，会特别麻烦！

例如，想要往数组中删除第三个元素，当完成删除后，还需要从删除元素位置遍历到最后一个元素位置，分别将它们都向前移动一个位置，也就是说后续的所有元素都要改变自己的位置，这是十分耗时的操作。——使用链表可更宽泛的定义数据

指针

在讲解链表之前，我们先要对指针有一定的了解，C++中的指针就像是一个地址的引用，它帮助你访问和操作存储在计算机内存中的数据。

理解起来是不是有点抽象，这里可以先把它理解为一个指示牌，这张指示牌上写着某个地方的地址。这个地址指向计算机内存中的一个特定位置，那里存储了一些数据。

想要声明指针，需要使用*符号，比如下面的代码。

int *ptr; // 声明一个指向整数的指针
// 也可以这样写
int* ptr;

指针想要存放某个变量的地址，需要先使用取地址符&获取地址

int x = 10;
int *ptr = &x; // 将指针初始化为变量x的地址

想要获取这个地址值，需要使用*符号来访问， 这个过程称为解引用

int value = *ptr; // 获取ptr指针指向的值（等于x的值，即10）

指针和数组之间有密切的关系，数组名本质上是一个指向数组第一个元素的指针。

int arr[3] = {1, 2, 3};
int *ptr = arr; // 数组名arr就是指向arr[0]的指针

指针还可以执行加法、减法等算术操作，以访问内存中的不同位置。

int arr[5] = {1, 2, 3, 4, 5};
int *ptr = arr; // 指向数组的第一个元素
int value = *(ptr + 2); // 获取数组的第三个元素（值为3）

除此之外，还有一个特殊的空指针值，通常表示为nullptr，用于表示指针不指向任何有效的内存地址。

int *ptr = nullptr; // 初始化为空指针

链表

与数组不同，链表的元素存储可以是连续的，也可以是不连续的，每个数据除了存储本身的信息（data数据域）之外，还存储一个指示着下一个元素的地址的信息（next指针域），给人的感受就好像这些元素是通过一条“链”串起来的。

链表的第一个节点的存储位置被称为头指针，然后通过next指针域找到下一个节点，直到找到最后一个节点，最后一个节点的next指针域并不存在，也就是“空”的，在C++中，用null来表示这个空指针。

为了简化链表的插入和删除操作，我们经常在链表的第一个节点前添加一个节点，称为虚拟头节点(dummyNode)，头节点的数据域可以是空的，但是指针域指向第一个节点的指针。

头指针是链表指向第一个节点的指针，访问链表的入口，经常使用头指针表示链表，头指针是链表必须的
头节点是为了方便操作添加的，不存储实际数据，头节点不一定是链表必须的

定义链表节点

那在C++中如何定义链表结构呢，传统的定义变量的方式只能使用一种数据类型，无法处理链表这种既包含数据域名、又包含指针域的复合结构，这就需要使用到struct结构体，结构体是一种用户自定义的数据类型，比如想要定义一个Person的结构体

// Person结构体
struct Person {
  // 使用 数据类型 成员变量的形式来定义
  int age; // int类型的年龄
  std::string name; // string类型的名字
}

结构体可以组合多个不同类型的成员变量，成员变量可以是各种数据类型，包括整数、浮点数、字符串、其他结构体等，所以你可以根据需要定义自己的结构体来组织数据。

// 链表节点结构体
struct ListNode {
    int val;  // 存储节点的数据
    ListNode *next; // 下一个节点也是链表节点，所以也是ListNode类型，*表示指针（地址），next是名称
}

但结构体只是个“模具”，创建的Person结构体虽然具有age、name，但它只是一个Person的概念，无法表示具体的人，只有将其“初始化”，比如”张三，18”, “李四、20”，才能真正的使用。

初始化结构体的方式有很多，这里我们使用构造函数的方式来进行，构造函数的名称与结构体的名称相同，和其他函数不一样的是，构造函数没有返回类型，除此之外类似于其他的函数，构造函数也有一个（可能为空）的参数列表和一个函数体（可能为空）。链表结构体的构造函数代码如下：

 ListNode(int x) : val(x), next(nullptr) {}

这里的ListNode(int x)表示定义一个接收整数参数 x的名称为ListNode的构造函数（名称和结构体相同），:表示初始化列表的开始，val(x)表示链表数据域的值被初始化为传递的参数 x ，next(nullptr)则表示

next指针被初始化为nullptr，表示没有下一个节点。

下面的完整代码定义了一个名为ListNode的结构体，用于表示链表中的一个节点，包含存储节点数据的数据域和存储下一个节点地址的指针域。

// 链表节点结构体
struct ListNode {
    int val;  // 存储节点的数据
    ListNode *next; // 指向下一个节点的指针	
  // 构造函数，用于初始化节点， x接收数据作为数据域，next(nullptr)表示next指针为空
    ListNode(int x) : val(x), next(nullptr) {}
};

链表的插入

上面我们完成了定义链表节点的操作，那应该完成怎样的操作将链表节点插入到链表的尾端，从而形成一个完整的链表呢？至少应该包括以下操作：

创建一个新的链表节点，初始化它的值为val

将新的节点放入到链表的尾部，接入链表，也就是当前链表的尾部的next指向新节点

新接入的链表节点变为链表的尾部

假设我们用cur来表示当前链表的尾节点

上面的操作用代码来表示如下：

ListNode *newNode = new ListNode(val); // 通过new构造一个新的节点,节点的值为val
cur -> next = newNode; // cur节点的next节点是新节点，从而将新节点接入链表
cur = cur -> next;      // 新插入的节点变更为新的尾节点，即cur发生了变更

这里有两个新的语法：new运算符和箭头语法->

new是一个运算符，它的作用就是在堆内存中动态分配内存空间，并返回分配内存的地址，使用方式一般为指针变量 = new 数据类型, 比如下面的代码

int *arr = new int[5]; // 分配一个包含5个整数的数组的内存空间，并返回一个地址，指针arr指向这个地址
delete [] arr;//记得释放，否则发生内存泄漏

箭头语法（->）：用于通过指针访问指针所指向的对象的成员，cur 是一个指向 ListNode结构体对象的指针，而 next 是 ListNode 结构体内部的一个成员变量（指向下一个节点的指针）。使用 cur->next 表示访问 cur 所指向的节点的 next 成员变量。