链表是一种非连续存储的线性数据结构，每个元素由数据域和指向下一个元素的指针域组成，C++实现链表的核心就是通过指针维护节点之间的连接关系。下面我们先看一张示意图，帮助理解链表的结构。
链表节点的定义
实现链表的第一步是定义节点结构体，每个节点需要包含存储数据的变量和指向下一个节点的指针，代码如下：
#include <iostream>
using namespace std;
// 定义链表节点结构体
struct ListNode {
int val; // 数据域，存储节点的值
ListNode* next; // 指针域，指向下一个节点
// 构造函数，初始化节点值和指针
ListNode(int x) : val(x), next(nullptr) {}
};
链表初始化
初始化链表可以创建一个头节点，头节点一般不存储实际数据，用来方便后续的操作，也可以直接创建第一个有效节点作为链表起点。下面是创建包含三个节点的链表的示例：
int main() {
// 创建三个节点，值分别为1、2、3
ListNode* node1 = new ListNode(1);
ListNode* node2 = new ListNode(2);
ListNode* node3 = new ListNode(3);
// 连接节点，形成链表 1->2->3
node1->next = node2;
node2->next = node3;
// 定义头指针指向第一个节点
ListNode* head = node1;
return 0;
}
链表遍历操作
遍历链表需要从头节点开始，依次通过next指针访问每个节点，直到遇到空指针为止，代码如下：
// 遍历链表并打印所有节点的值
void printList(ListNode* head) {
ListNode* cur = head; // 临时指针指向当前节点
while (cur != nullptr) {
cout << cur->val << " ";
cur = cur->next; // 移动到下一个节点
}
cout << endl;
}
链表插入节点
链表插入节点分为头部插入、中间插入和尾部插入，这里以头部插入为例，新节点会成为新的头节点：
// 在链表头部插入新节点
void insertAtHead(ListNode*& head, int val) {
ListNode* newNode = new ListNode(val); // 创建新节点
newNode->next = head; // 新节点的next指向原来的头节点
head = newNode; // 头指针指向新节点
}
链表删除节点
删除节点需要先找到要删除节点的前一个节点，然后修改前一个节点的next指针，跳过要删除的节点，这里以删除第一个值为指定值的节点为例：
// 删除链表中第一个值为val的节点
void deleteNode(ListNode*& head, int val) {
// 如果头节点就是要删除的节点
if (head != nullptr && head->val == val) {
ListNode* temp = head;
head = head->next;
delete temp; // 释放节点内存
return;
}
// 查找要删除节点的前一个节点
ListNode* cur = head;
while (cur != nullptr && cur->next != nullptr) {
if (cur->next->val == val) {
ListNode* temp = cur->next;
cur->next = cur->next->next;
delete temp;
return;
}
cur = cur->next;
}
}
注意事项
- 使用
new关键字创建的节点，在不再使用时要通过delete释放内存，避免内存泄漏 - 操作指针时要先判断指针是否为空，避免访问空指针导致程序崩溃
- 修改头指针时，函数参数要使用指针的引用
ListNode*&，否则无法修改外部的实参