一.链表基础（单链表）
1. 物理结构与逻辑结构
逻辑结构：线性结构，元素一个接一个排列。
物理结构：非连续、非顺序存储。各节点独立分布在内存（堆）中。
比喻：火车车厢。每节车厢独立，通过挂钩（指针）连接，可灵活增删车厢。
2. 节点（Node）结构
单链表每个节点包含两个域：
数据域：存储实际数据（如
int data）指针域：存储下一个节点的地址，称为“后继指针”或
next// 数据类型重定义，便于后续修改存储的数据类型
typedef int SLTDataType;// 单链表节点结构体
typedef struct SListNode {
SLTDataType data; // 存储的数据
struct SListNode* next; // 指向下一个节点的指针
} SLTNode;next指针的类型必须是struct SListNode*。因为它指向的是下一个同类型的节点。这是链表定义的核心，不可以使用SLTNode* next; ------->编译报错！C语言编译器是向上编译的，不能在结构体内部使用结构体别名。此时 SLTNode 还未被定义
定义加打印函数测试：
3. 头指针与空链表
头指针：一个指向第一个节点的指针（如
struct SListNode* plist）。空链表：头指针
plist == NULL，表示链表不存在任何节点。按需申请释放节点，无空间浪费。
插入删除节点只需修改指针指向，头部操作时间复杂度为O(1)。
不支持随机访问，查找元素需从头遍历。
特性 | 顺序表 | 单链表 |
|---|---|---|
初始化 | 需要初始化容量(size)和大小(capacity) | 无需初始化 |
空状态 | 数组指针为NULL，或size=0 | 头指针 |
原因 | 底层是连续数组，需要管理内存空间 | 节点离散分布，只需管理头指针 |
4.二级指针传参深度解析
核心原理：形参的改变不影响实参，若要修改实参的值，必须传递实参的地址。
1. 误区纠正
错误认知：看到形参是
一级指针就认为是“传地址”。正确认知：
无论是指针变量还是普通变量，都是内存中的变量，都有属于自己的地址。
传地址的标志：必须使用取地址符
&（数组名除外，因为数组名本身代表首元素地址）。若传
plist（一级指针），传的是该指针变量存储的值（即某个节点的地址）；若要修改plist本身，使其指向新节点，必须传&plist（一级指针的地址）。
2. 类比理解
变量 | 类型 | 存储的值 | 自身地址 |
|---|---|---|---|
|
|
|
|
|
|
|
|
修改
a的值，需传&a(0x100) 给int*接收。修改
pa的值，需传&pa(0x800) 给int**接收。
二.单链表的操作
（1）尾插
算法思路：
申请新节点。
若链表为空（
phead == NULL），直接将新节点作为头节点。若链表非空，遍历找到尾节点（尾节点特征：
next == NULL），将尾节点的next指向新节点。
易错点（重点）：
参数必须传二级指针：因为可能需要修改头指针本身（如空链表插入时）。如果传一级指针
SLTNode* phead，函数内修改的是形参，实参不会改变。若链表为空，插入第一个节点时需要改变头指针
plist的指向。结论：凡是可能改变头指针指向的函数（如头插、尾插、头删、尾删），形参必须设计为**二级指针SLTNode**。找尾循环条件：必须是
ptail->next != NULL，而非ptail != NULL。如果使用后者，循环结束时ptail为NULL，无法连接新节点。
（2）头插
算法思路：
创建新节点
newNode。将
newNode的next指向原头节点*pphead。将头指针
*pphead指向newNode。
（3）尾删
算法思路
断言检查：链表不能为空（
*pphead != NULL）。特殊情况：若只有一个节点（
(*pphead)->next == NULL），直接释放头节点并置空。一般情况：
定义两个指针，
ptail指向当前节点，prev指向ptail的前一个节点。遍历链表，找到尾节点
ptail。将
prev的next置为NULL。释放
ptail。
（4）头删
算法思路
断言检查：链表不能为空。
保存原头节点的下一个节点地址（
next）。释放原头节点。
将头指针
*pphead指向保存的next节点
（5）查找
算法思路
遍历链表，比较当前节点数据与目标值
x。找到则返回该节点指针，否则返回
NULL。
（6）在指定位置前插入
算法思路：
断言：
pphead和pos均不能为空。特殊情况：若
pos恰好是头节点（即*pphead == pos），直接调用头插函数。一般情况：
定义
prev指针，遍历找到pos的前一个节点。创建新节点
newnode。建立链接：
prev->next = newnode; newnode->next = pos;
（7）在指定位置之后插入节点
算法思路：
已知pos节点，要插入数据为x的新节点newNode：
- 通过
SLTBuyNode(x)创建新节点 - 先让
newNode->next指向pos->next（即原后继节点） - 后让
pos->next指向newNode
易错点:
// 错误：先改 pos->next，会导致原后继节点丢失
pos->next = newNode;
newNode->next = pos->next; // 此时 pos->next 已经是 newNode，相当于自指！
重点：如果先执行pos->next = newNode，那么pos->next的指向已经发生改变了，此时再通过pos->next去找原来的后继节点（如节点"4"）就找不到了，导致链表断裂。newNode->next会指向newNode自身，原后继节点无法访问。
正确：
先连后面，再连前面
newNode->next = pos->next; // 第一步：newNode 指向原 pos 的后继
pos->next = newNode; // 第二步：pos 指向 newNode
(8)删除指定位置的节点
算法思路：
已知pos节点，要删除它：
- 如果
pos是头节点 → 执行头删 - 否则 → 从头遍历找
pos的前驱prev - 先让
prev->next指向pos->next（跨过pos） - 后
free(pos)并将pos置为NULL
易错点1：删除头节点需要特殊处理
如果pos恰好是头节点，从头开始找前驱的代码会失效——prev永远找不到prev->next == pos，会导致死循环或对空指针解引用崩溃。必须单独判断pos == *pphead走头删逻辑。
易错点2：必须先改指针再释放
如果先free(pos)，则pos变成野指针，无法再通过pos->next获取后继节点地址，链表断裂。所以必须先让前驱跨接，再释放pos。
（9）删除指定位置之后的节点
算法思路
已知pos节点，要删除pos->next：
- 用
del指针保存pos->next（即待删节点） - 让
pos->next指向del->next（跨过待删节点） free(del)并将del置为NULL相较删除指定位置节点，删除其后继无需找前驱，效率更优——这是链表相比顺序表的重要优势。
易错点：pos->next必须非空
删除pos之后的节点，不仅要求pos不能为空，pos->next也不能为空。如果pos是尾节点（pos->next == NULL），没有后继可删，必须断言assert(pos->next)拦截，否则del为空，free(NULL)虽不崩溃但逻辑错误。
（10）销毁链表
算法思路：
逐个释放所有节点，最后将头指针置NULL：
- 定义
pcur指向头节点，next保存下一节点 - 循环：保存
pcur->next→free(pcur)→pcur移到下一节点 - 循环结束，将
*pphead置为NULL
易错点1：必须用二级指针
销毁链表需要将头指针本身置为NULL，所以要传头指针的地址（二级指针SLTNode** pphead），否则修改不会影响实参。
易错点2：释放前必须先保存后继
如果先free(pcur)再访问pcur->next，pcur已是野指针，无法找到下一个节点。所以必须在释放前用next保存pcur->next。
关于free后是否置NULL的讨论
- 函数内的局部变量（如
pcur、next）跳出作用域自动销毁，不置NULL不影响程序正确性 - 但养成良好习惯：
free后将指针置NULL，可避免后续误用时对野指针解引用 - 对于传递给函数的外部指针（如
pos），free后置NULL是必要习惯
