目录
什么是链表？
链表是一种线性数据结构，就像数组一样，可以按顺序存储元素，但它的实现方式和数组完全不同：
| 对比点 | 数组（Array） | 链表（Linked List） |
|---|---|---|
| 存储结构 | 连续内存，元素按索引访问 | 不连续内存，每个节点包含指针 |
| 插入/删除 | 慢（可能需要移动元素） | 快（只需修改指针） |
| 随机访问 | 支持 O(1) 访问 | 不支持（只能从头一个个走） |
链表的结构（单链表）
每个节点（Node）都包含两个部分：
值（val）
指针（next）指向下一个节点
struct ListNode {
int val; // 存储的数据
ListNode* next; // 指向下一个节点的指针
ListNode(int x) : val(x), next(nullptr) {}
};带头节点的链表
这种情况下，头节点是一个不存储实际数据的节点，其 val 通常无意义，主要作用是简化链表操作（如插入、删除首节点时无需特殊处理）
此时真正的第一个数据节点是头节点的 next 指向的节点。
不带头节点的链表
这种情况下，头节点就是链表中第一个存储实际数据的节点，其 val 是有意义的，直接表示链表的第一个元素。
// 不带头结点的链表（头指针直接指向第一个数据节点）
ListNode* head = new ListNode(1); // head->val = 1（有实际意义）
// 带头结点的链表（头结点不存数据）
ListNode* dummy = new ListNode(0); // dummy->val 无意义
dummy->next = new ListNode(1); // 第一个数据节点链表常见分类
| 类型 | 特点 |
|---|---|
| 单链表 | 每个节点只指向下一个节点 |
| 双向链表 | 每个节点有两个指针，指向前一个和后一个节点 |
| 循环链表 | 尾节点的指针指向头节点，形成一个闭环 |
链表题型分类
| 类型 | 核心思想/技巧 | 代表题目（LeetCode） |
|---|---|---|
| 1. 基础遍历与操作 | 遍历链表、删除、插入、查找节点等 | 203、83、21 |
| 2. 快慢指针 | 判断环、找中点、删除倒数第 N 个节点等 | 141、876、19 |
| 3. 链表反转 | 局部反转 / 整体反转，迭代或递归 | 206、92、25 |
| 4. 合并与拆分 | 合并两个 / K 个有序链表，分割链表等 | 21、23、86 |
| 5. 判断性质（是否回文等） | 快慢指针 + 栈 / 反转+比较 | 234、143 |
| 6. 环形链表 & 交点 | 是否成环，环的起点，两个链表相交点等 | 141、142、160 |
基础遍历与操作
遍历链表
思路：链表不像数组那样可以用下标访问，只能通过指针从头一个个向后走。
ListNode* cur = head;
while (cur != nullptr) {
cout << cur->val << " ";
cur = cur->next; // 访问下一个节点
}插入节点
假设要在节点 1 和节点 2 之间插入新节点 x。
原链表： [1] → [2] → ...
插入后： [1] → [x] → [2] → ...
操作步骤（用 prev 表示 [1] 节点）：
ListNode* x = new ListNode(99); // 创建新节点
x->next = prev->next; // 第一步：新节点连到原来的下一个
prev->next = x; // 第二步：前一个节点连到新节点删除节点（关键：prev->next = cur->next）
假设要删除值为 2 的节点（cur 指向 2，prev 是前一个节点）
prev->next = cur->next; // 前一个节点跳过 cur，直接连到 cur 后面
delete cur; // 删除节点，释放内存虚拟头结点 dummy 的应用
dummy 解决的问题：当要删除头结点时，没有前一个节点 prev，代码会很复杂。
删除值为 1 的头结点
ListNode* dummy = new ListNode(-1); // dummy不存储真正数据
dummy->next = head;
ListNode* cur = dummy;
while (cur->next != nullptr) { // 循环条件是cur的下一个节点存在
if (cur->next->val == target) {
ListNode* toDelete = cur->next;
cur->next = cur->next->next;
delete toDelete;
} else {
cur = cur->next;
}
}
return dummy->next;LeetCode 203 移除链表元素
思路：
这个题目关键的点就是要考虑删除“头节点”和中间节点的情况
所以使用 dummy 虚拟头节点简化代码处理
步骤：
1. 创建 dummy 节点，指向原 head
2. 从 dummy 开始遍历，判断当前 cur->next->val 是否等于 val
是：删除它
否：继续往下走
3. 返回 dummy->next 作为新的链表头
ListNode* removeElements(ListNode* head, int val) {
ListNode* dummy = new ListNode(-1);
dummy->next = head;
ListNode* cur = dummy;
while (cur->next != nullptr) {
if (cur->next->val == val) {
ListNode* temp = cur->next;
cur->next = cur->next->next;
delete temp;
} else {
cur = cur->next;
}
}
ListNode* newHead = dummy->next;
delete dummy; // 删除 dummy 节点，释放内存
return newHead;
}LeetCode 83 删除排序链表中的重复元素
思路：
1. 由于链表已经是升序排序的，因此 重复元素一定是连续的。
2. 只需要比较当前节点 cur 和它的下一个节点 cur->next 的值是否相同：
是，就跳过：cur->next = cur->next->next
否，就继续向后移动 cur
不需要 dummy 虚拟头结点
因为不会删头结点，也不用返回 dummy->next，只操作当前节点。
ListNode* deleteDuplicates(ListNode* head) {
ListNode* cur = head;
while (cur != nullptr && cur->next != nullptr) {
if (cur->val == cur->next->val) {
ListNode* temp = cur->next;
cur->next = cur->next->next;
delete temp;
} else {
cur = cur->next;
}
}
return head;
}LeetCode 21 合并两个有序链表
思路：
这道题其实就是用两个指针分别指向两个链表，每次取当前两个节点中较小的一个接到新链表后面，然后往后移动那个被取的指针。
类似归并排序中的合并过程。
解法一：迭代 + dummy 虚拟头结点
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* dummy = new ListNode(-1);
ListNode* tail = dummy;
while (l1 != nullptr && l2 != nullptr) {
if (l1->val <= l2->val) {
tail->next = l1;
l1 = l1->next;
} else {
tail->next = l2;
l2 = l2->next;
}
tail = tail->next;
}
// 处理剩下的部分
tail->next = (l1 != nullptr) ? l1 : l2;
ListNode* result = dummy->next;
delete dummy;
return result;
}dummy →
↑
tail每次比较 l1 和 l2 的当前值：
小的接到 tail 后面
tail 往后走
被选的那个链表指针也往后走
解法二：递归方式（更简洁）
下面的代码会用到递归，如果不懂，可以先看下面一个简单的例子：
int test(int x) {
if (x == 0) return 0;
int y = test(x - 1);
return x + y;
}计算 test(3) 的结果：
从 x=3 开始，逐层递归调用，直到最底层后再回溯计算：
test(3)：
调用 test(2)，得到 y = test(2)，返回 3 + test(2) ，这里等待返回值填入y，然后return x + y
test(2)：
调用 test(1)，得到 y = test(1)，返回 2 + test(1)
test(1)：
调用 test(0)，得到 y = test(0)，返回 1 + test(0)
test(0)：
递归终止，即 test(0) = 0
test(1) = 1 + test(0) = 1 + 0 = 1
test(2) = 2 + test(1) = 2 + 1 = 3
test(3) = 3 + test(2) = 3 + 3 = 6
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if (l1 == nullptr) return l2;
if (l2 == nullptr) return l1;
if (l1->val <= l2->val) {
l1->next = mergeTwoLists(l1->next, l2);
return l1;
} else {
l2->next = mergeTwoLists(l1, l2->next);
return l2;
}
}快慢指针
若是对快慢指针不了解，可点击下面链接查看
双指针[对撞指针+快慢指针+Leetcode例题练习]-CSDN博客
LeetCode 141 环形链表
思路：快慢指针
使用两个指针：
slow 每次走一步
fast 每次走两步
如果链表有环，fast 会在环中追上slow ⇒ 相遇
如果链表无环，fast 会先走到 nullptr ⇒ 结束
bool hasCycle(ListNode* head) {
ListNode* slow = head;
ListNode* fast = head;
while (fast != nullptr && fast->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) return true; // 相遇表示有环
}
return false;
}LeetCode 876 链表的中间节点
思路：快慢指针找中点
初始化两个指针：
slow 每次走一步
fast 每次走两步
当 fast 到达尾部时，slow 恰好在中间
举个例子：head = [1,2,3,4,5,6]
| 步骤 | fast 走到 | slow 走到 |
|---|---|---|
| step 1 | 3 | 2 |
| step 2 | 5 | 3 |
| step 3 | null | 4 中点 |
在题目的案例中有讲到这个例子。该链表有两个中间结点，值分别为 3 和 4 ，返回第二个结点。
ListNode* middleNode(ListNode* head) {
ListNode* slow = head;
ListNode* fast = head;
while (fast != nullptr && fast->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}LeetCode 19 删除链表的倒数第 N 个节点
思路：快慢指针 + 虚拟头节点 dummy
用 fast 先走 n + 1 步
然后 slow 和 fast 一起走
当 fast 到达末尾，slow 正好停在待删除节点的前一个节点
举个例子：
链表：[1 → 2 → 3 → 4 → 5]
目标：删除倒数第 2 个，即节点 4
过程：
fast 先走 2 步 → 到 3
slow 从 dummy 开始
fast 和 slow 一起走：
fast: 3 → 4 → 5 → null
slow: dummy → 1 → 2 → 3（停在这里）此时 slow->next = 4（要删除的节点）
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummy = new ListNode(-1);
dummy->next = head;
ListNode* fast = dummy;
ListNode* slow = dummy;
// fast 先走 n+1 步
for (int i = 0; i <= n; ++i) {
fast = fast->next;
}
// fast 和 slow 一起走
while (fast != nullptr) {
fast = fast->next;
slow = slow->next;
}
// 删除 slow->next
ListNode* toDelete = slow->next;
slow->next = slow->next->next;
delete toDelete;
ListNode* result = dummy->next;
delete dummy;
return result;
}创建虚拟头节点是为了避免头结点被删时出问题
链表反转
| 类别 | 说明 | 题目 |
|---|---|---|
| 整体反转 | 反转整个链表 | LeetCode 206 |
| 区间反转 | 只反转一部分链表（第 m 到 n 个节点） | LeetCode 92 |
| K 组反转 | 每 k 个节点一组进行反转 | LeetCode 25 |
LeetCode 206 反转链表
解法一：迭代
思路：
使用三个指针来实现反转过程：
| 指针名 | 说明 |
|---|---|
| prev | 当前节点的前一个节点 |
| cur | 当前正在处理的节点 |
| next | 记录 cur 的下一个节点（防丢） |
ListNode* reverseList(ListNode* head) {
ListNode* prev = nullptr;
ListNode* cur = head;
while (cur != nullptr) {
ListNode* next = cur->next;
cur->next = prev; // 反转指向
prev = cur;
cur = next;
}
return prev;
}举个例子：
假设有一个链表：1 -> 2 -> 3 -> 4 -> 5 -> null
初始状态：
prev = null
cur = 1 (指向链表头节点)
第一次循环 (cur = 1)：ListNode* next = cur->next;
next 指向 2 (保存当前节点的下一个节点)
cur->next = prev;
1 的 next 指向 null (完成 1 的反转)
此时链表结构：1 -> null, 2 -> 3 -> 4 -> 5 -> null
prev = cur;
prev 移动到 1 (现在 prev 指向已反转部分的头)
cur = next;
cur 移动到 2 (继续处理下一个节点)第二次循环 (cur = 2)：
ListNode* next = cur->next;
next 指向 3
cur->next = prev;
2 的 next 指向 1 (完成 2 的反转)
此时链表结构：2 -> 1 -> null, 3 -> 4 -> 5 -> null
prev = cur;
prev 移动到 2
cur = next;
cur 移动到 3
······
解法二：递归
ListNode* reverseList(ListNode* head) {
if (head == nullptr || head->next == nullptr) return head;
ListNode* newHead = reverseList(head->next);
head->next->next = head;
head->next = nullptr;
return newHead;
}计算 reverseList(1) 的结果（1 是链表的头节点）：
从 head=1 开始，逐层递归调用，直到最底层后再回溯计算：
reverseList(1)：
因为 head≠null 且 head->next=2≠null，不满足终止条件
调用 reverseList(2)，得到 newHead = reverseList(2)
等待 reverseList(2) 返回结果后，执行 head->next->next = head（即 2->next = 1）和 head->next = null（即 1->next = null）
最终返回 newHead（即 reverseList(2) 的返回值）
reverseList(2)：
因为 head≠null 且 head->next=3≠null，不满足终止条件
调用 reverseList(3)，得到 newHead = reverseList(3)
等待 reverseList(3) 返回结果后，执行 head->next->next = head（即 3->next = 2）和 head->next = null（即 2->next = null）
最终返回 newHead（即 reverseList(3) 的返回值）
reverseList(3)：
因为 head≠null 但 head->next=null，满足终止条件
直接返回 head（即节点 3）
回溯阶段：
reverseList(3) 返回 3，所以 reverseList(2) 中的 newHead=3
reverseList(2) 执行完反转操作后返回 3，所以 reverseList(1) 中的 newHead=3
reverseList(1) 执行完反转操作后返回 3
最终结果：reverseList(1) 的返回值是 3，此时链表已反转为 3 → 2 → 1 → null
LeetCode 92 反转链表 II
思路：
使用一个 dummy 节点指向头，方便处理边界
找到 left 节点的前一个节点 pre
使用头插法（插入在 pre 后）来反转 left 到 right 区间的节点
接好前后链
ListNode* reverseBetween(ListNode* head, int left, int right) {
ListNode* dummy = new ListNode(-1);
dummy->next = head;
ListNode* pre = dummy;
// 找到 left 前的那个节点（pre）
for (int i = 1; i < left; ++i) {
pre = pre->next;
}
// 区间反转（头插法）
ListNode* cur = pre->next;
for (int i = 0; i < right - left; ++i) {
ListNode* temp = cur->next;
cur->next = temp->next;
temp->next = pre->next;
pre->next = temp;
}
ListNode* result = dummy->next;
delete dummy;
return result;
}假设链表为 1 → 2 → 3 → 4 → 5 → null，要反转的区间是 left=2 到 right=4
（反转 2 → 3 → 4 这部分）
循环执行 right-left=2 次（i=0 和 i=1）：
第 1 次循环（i=0）：
ListNode* temp = cur->next;
temp 指向 3（保存 cur 的下一个节点）
cur->next = temp->next;
2->next = 4（让 2 跳过 3 直接指向 4）
此时链表：1 → 2 → 4 → 5 → null，而 3 暂时游离
temp->next = pre->next;
3->next = 2（让 3 指向 pre 的下一个节点，也就是 2）
pre->next = temp;
1->next = 3（让 pre 指向 temp，即 3 成为区间新的第一个节点）
此时链表：1 → 3 → 2 → 4 → 5 → null
第 2 次循环（i=1）：
ListNode* temp = cur->next;
temp 指向 4（此时 cur 仍为 2，cur->next 是 4）
cur->next = temp->next;
2->next = 5（让 2 跳过 4 直接指向 5）
此时链表：1 → 3 → 2 → 5 → null，而 4 暂时游离
temp->next = pre->next;
4->next = 3（让 4 指向 pre 的下一个节点，也就是 3）
pre->next = temp;
1->next = 4（让 pre 指向 temp，即 4 成为区间新的第一个节点）
此时链表：1 → 4 → 3 → 2 → 5 → null
合并与拆分
合并两个链表的题有LeetCode 21，上面已经做过，思路就是双指针比较值 + 拼接
LeetCode 86 分隔链表
思路：链表拆成两个再合并
用两个虚拟头结点：
smallHead：保存小于 x 的节点
largeHead：保存大于等于 x 的节点
遍历原链表，把每个节点分类接入两个链表尾部
最后将 small 链表尾部接上 large 链表的头，构成新链表
ListNode* partition(ListNode* head, int x) {
ListNode* smallHead = new ListNode(-1);
ListNode* largeHead = new ListNode(-1);
ListNode* small = smallHead;
ListNode* large = largeHead;
ListNode* cur = head;
while (cur != nullptr) {
if (cur->val < x) {
small->next = cur;
small = small->next;
} else {
large->next = cur;
large = large->next;
}
cur = cur->next;
}
large->next = nullptr; // 防止形成环
small->next = largeHead->next; // 拼接两个链表
ListNode* result = smallHead->next;
delete smallHead;
delete largeHead;
return result;
}尚未完结