链表题型核心总结

一、三道典型题目梳理
题目 1：无表头单向链表 - 输入终止 + 顺序输出
题目要求：输入若干个学生的信息（学号、姓名、成绩），当输入学号为 0 时结束，用单向链表组织这些学生信息后，再按顺序输出。
核心场景：无表头链表构建、输入终止条件判断（学号为 0）、链表顺序遍历输出。
题目 2：无表头单向链表 - 删除偶数节点
题目要求：输入若干个正整数（输入 - 1 为结束标志），建立一个单向链表，将其中的偶数值结点删除后输出。链表节点定义为struct Node{int data; struct Node *next;}。
核心场景：无表头链表构建、节点遍历、指定条件（偶数）节点删除、内存释放。
题目 3：带头结点单向链表 - 0 终止 + 格式输出
题目要求：建立一个带头结点的单向链表，链表中每个结点包含整型数据域和指针域，结点的数据域值依次从键盘输入（以 0 表示输入结束且 0 不存储在链表中），按指定格式输出链表的数值（提示语 + 数值行，严格控制空格 / 换行）。
核心场景：带头节点链表构建、输入终止判断（0）、严格格式输出（空格 / 换行 / 提示语）。
二、核心共性与解题流程
1. 共性特征
链表构建方式：均采用「尾插法」构建链表，保证输入顺序与链表存储顺序一致；
输入规则：都有明确的 “终止符”（0/-1），需先判断终止符再决定是否存储，终止符不存入链表；
核心流程：构建链表 → 处理链表（遍历/删节点） → 格式输出 → 释放内存；
内存管理：均需通过new创建节点，最终遍历释放所有节点内存（避免内存泄漏）；
输出要求：均需严格控制格式（空格、换行、提示语），是 OJ 判题的高频丢分点。
2. 通用解题流程
步骤 核心操作
链表初始化 区分 “带头节点” 和 “无表头节点” 两种初始化方式（见下文）；
构建链表 尾插法循环读入数据，遇到终止符则停止，逐个创建节点并插入链表尾部；
链表处理 按需遍历（仅输出）或遍历 + 删除（指定条件节点）；
格式输出 按题目要求控制空格、换行、提示语（如 “每个数后加空格”“无末尾空格” 等）；
内存释放 遍历链表，逐个释放节点内存（包括头节点）；
三、核心考点与关键实现
1. 链表初始化（带头 / 不带头）
链表类型 初始化代码 适用场景
无表头节点 Node *head = nullptr, *tail = nullptr; 题目 1、题目 2
带头节点 Node *head = new Node; head->next = nullptr; Node *tail = head; 题目 3（简化空链表处理）
2. 尾插法构建链表（通用）
cpp
运行
int val;
while (cin >> val) {
// 终止符判断（按题目调整：0/-1）
if (val == 0 || val == -1) break;
// 创建新节点
Node *newNode = new Node;
newNode->data = val; // 题目1需扩展为学号/姓名/成绩
newNode->next = nullptr;
// 尾插法插入
if (head == nullptr) { // 无表头：空链表判断
head = newNode;
tail = newNode;
} else {
tail->next = newNode;
tail = newNode;
}
}
3. 节点操作（遍历 / 删除）
（1）链表遍历（输出）
cpp
运行
// 无表头：从head开始
Node *cur = head;
// 带头节点：跳过头节点（头节点不存数据）
// Node *cur = head->next;
while (cur != nullptr) {
cout << cur->data; // 按题目扩展输出（如姓名、多成绩）
// 格式控制：按题目要求加空格/换行
if (cur->next != nullptr) cout << " ";
cur = cur->next;
}
（2）指定条件节点删除（题目 2 核心）
cpp
运行
Node *cur = head, *pre = nullptr;
while (cur != nullptr) {
if (cur->data % 2 == 0) { // 删除条件：偶数
Node *temp = cur;
// 区分头节点删除和中间/尾节点删除
if (pre == nullptr) head = cur->next; // 删除头节点
else pre->next = cur->next; // 删除中间/尾节点
cur = cur->next;
delete temp; // 释放删除节点内存
} else {
pre = cur;
cur = cur->next;
}
}
4. 格式输出（避坑重点）
格式要求 实现方案 对应题目
无末尾空格 先输出第一个节点，后续节点前加空格 题目 3（标准版）
每个数后加空格 直接cout << data << " "; 题目 3（特殊要求版）
提示语单独换行 cout << "The data of link:" << endl; 题目 3
5. 内存释放（通用）
cpp
运行
Node *cur = head;
while (cur != nullptr) {
Node *temp = cur;
cur = cur->next;
delete temp; // 逐个释放节点
}
四、高频易错点与避坑指南
表头混淆：带头节点链表遍历需从head->next开始，否则会处理头节点的空数据；
格式错误：末尾空格 / 换行是 OJ 判题的核心丢分点，需严格匹配题目样例（如题目 3 需确认 “最后一个数后是否加空格”）；
终止符处理：终止符（0/-1）需 “先判断再存储”，避免将终止符存入链表；
内存泄漏：新建节点后未释放、删除节点后未释放、带头节点链表漏释放头节点，均会导致内存泄漏；
指针操作：删除节点时需先暂存节点指针，再移动遍历指针，避免野指针。
五、总结
链表基础题的核心是「掌握链表构建（尾插法）+ 节点操作（遍历 / 删除）+ 格式控制 + 内存管理」，其中：
尾插法是构建链表的最优方式，需熟练区分带头 / 不带头节点的初始化；
节点删除的关键是区分 “头节点” 和 “中间 / 尾节点” 的删除逻辑；
格式输出需严格对齐题目样例，重点关注空格和换行；
内存释放是必考点，无论题目是否明确要求，都需遍历释放所有节点。