这是一个非常棒的复习方向。链表（Linked List）是数据结构期末考试中必考且分值较高的模块，通常出现在选择题（考察复杂度）、代码填空题（考察指针操作）和算法大题（手写完整逻辑）中。

数据结构期末复习笔记：链表 (Linked List)

一、核心考点梳理

1. 链表 vs 数组 (核心理论)

这是选择题和简答题的高频考点，必须熟记两者的区别。

特性	数组 (Array)	链表 (Linked List)
内存存储	连续内存空间	离散内存空间，通过指针连接
随机访问	支持，$O(1)$	不支持，需要遍历，$O(n)$
插入/删除	效率低，需移动元素，$O(n)$	效率高，仅需修改指针，$O(1)$ (前提是已知位置)
空间利用	可能有碎片或预分配浪费	动态分配，但每个节点需额外存储指针

2. 常见链表类型

单链表 (Singly Linked List): 节点包含 data 和 next。
双向链表 (Doubly Linked List): 节点包含 data、prev 和 next。删除节点更方便（因为能找到前驱）。
循环链表 (Circular Linked List): 尾节点的 next 指向头节点。常用于解决约瑟夫环（Josephus）问题。

3. 代码实战技巧 (这也是扣分点！)

在手写代码（算法题）时，老师最看重以下细节：

虚拟头节点 (Dummy Head / Sentinel):
- 用途: 在处理头节点可能发生变化的题目（如删除头节点、合并链表）时，创建一个 dummy 节点指向 head，可以统一逻辑，避免单独处理头节点为空的情况。
空指针异常 (Null Pointer Exception):
- 检查: 访问 p->next 之前，必须确保 p 不为 NULL。
- 常见错误: while(p->next != NULL) 如果 p 本身是空，程序直接崩溃。
断链顺序:
- 口诀: "先连后断"。插入节点时，先将新节点的 next 指向后继，再将前驱的 next 指向新节点。

二、经典题型与解题模板

期末考试中，链表的题目万变不离其宗，主要考察以下几种思维模式：

1. 指针修改类 (基础)

考点: 插入、删除、反转。
难点: 很容易丢失节点，导致内存泄漏或断链。
核心: 熟练掌握 temp 临时指针的使用。

2. 快慢指针 (Fast & Slow Pointers) - 必考技巧

场景:
1. 判断链表是否有环: 快指针走两步，慢指针走一步，相遇则有环。
2. 寻找链表中点: 快指针走两步，慢指针走一步，快指针到终点时，慢指针在中点（常用于归并排序链表）。
3. 寻找倒数第 K 个节点: 快指针先走 K 步，然后两指针同速走。

3. 链表合并与分割

场景: 归并两个有序链表（递归或迭代）。

三、 LeetCode 经典题目清单 (按复习优先级排序)

建议按照以下顺序刷题，涵盖了90%的链表考点。

Level 1: 基础必会 (送分题不能丢)

1. [206] 反转链表 (Reverse Linked List)

206. 反转链表 - 力扣（LeetCode）

重要性: ⭐⭐⭐⭐⭐ (默写级别)
题意: 将单链表反转。
思路:
- 迭代法: 双指针 prev 和 curr，每次保存 curr->next，然后 curr->next = prev，推进指针。
- 递归法: 理解起来稍难，但代码极简。

关键代码 (C++):

ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* curr = head;
    while (curr != nullptr) {
        ListNode* nextTemp = curr->next; // 存一下，防止断链
        curr->next = prev;               // 反转
        prev = curr;                     // 步进
        curr = nextTemp;                 // 步进
    }
    return prev;
}

2. [21] 合并两个有序链表 (Merge Two Sorted Lists)

21. 合并两个有序链表 - 力扣（LeetCode）

重要性: ⭐⭐⭐⭐⭐
思路: 使用 虚拟头节点 (Dummy Head)。比较两个链表的头，谁小连谁，最后把剩余的链表接上。

Level 2: 进阶技巧 (快慢指针与数学)

3. [141] 环形链表 (Linked List Cycle)

重要性: ⭐⭐⭐⭐
思路: 快慢指针。slow 走一步，fast 走两步。如果 fast 遇到 NULL，无环；如果 fast == slow，有环。

4. [19] 删除链表的倒数第 N 个结点

重要性: ⭐⭐⭐⭐
思路: 双指针。让 fast 先走 $N+1$ 步（或者 $N$ 步，取决于是否用虚拟头），然后 fast 和 slow 同时走。当 fast 到末尾，slow 正好在待删除节点的前一个位置。

5. [160] 相交链表 (Intersection of Two Linked Lists)

重要性: ⭐⭐⭐
思路:
- 方法A: 计算长度差，长链表先走差值步，然后一起走。
- 方法B (浪漫解法): 指针 A 走完链表 A 去走 B，指针 B 走完链表 B 去走 A。若相交，必会在交点相遇（$a + c + b = b + c + a$）。

Level 3: 综合大题 (拿高分关键)

6. [142] 环形链表 II (Linked List Cycle II)

重要性: ⭐⭐⭐
考点: 不仅判断有环，还要找环的入口。
结论: 快慢指针相遇后，一个指针从头走，一个从相遇点走，每次一步，再次相遇点即为入口。

7. [234] 回文链表 (Palindrome Linked List)

重要性: ⭐⭐⭐
思路: 综合题。
1. 快慢指针找中点。
2. 反转后半部分链表。
3. 前后两半链表逐个比较。

四、考前复习自测清单

在去考场前，请确认你能回答以下问题：

[ ] 如何用 $O(1)$ 时间复杂度删除一个非头尾的节点（前提是只给你这个节点的指针，且不允许访问前驱）？
- 答案: 将下一个节点的值复制到当前节点，然后删除下一个节点（狸猫换太子）。
[ ] 为什么链表反转需要三个指针（或者两个指针加一个临时变量）？
[ ] 在写 p->next->next 这种代码时，你需要检查什么？
- 答案: 需要检查 p 是否为空，以及 p->next 是否为空。

祝你期末考试顺利，链表题目全对！