菜鸟笔记在算法面试中，链表是当之无愧的“高频考点”——它结构简单但灵活性强，能有效考察候选人的指针操作、逻辑思维和边界处理能力。本文精选 9 道链表经典面试题，从基础到进阶，涵盖快慢指针、双指针、递归等核心技巧。每道题都包含详细的解题思路、图解分析和完整的 C++ 代码实现。
注：本文所有题目均基于单链表（最常见面试场景），统一定义 C++ 链表节点结构如下（面试中可直接复用，无需额外说明）：
// 链表节点结构（C++）
struct ListNode {
int val; // 节点值
ListNode *next; // 指向下一节点的指针
ListNode(int x) : val(x), next(nullptr) {
} // 构造函数
};
一、反转链表
LeetCode 206. 反转链表
题目描述
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例：
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
解题思路
方法一：迭代法
核心思想：使用三个指针 prev、current、next，依次改变每个节点的指向。
图解过程：
初始状态：
NULL <- 1 2 -> 3 -> 4 -> 5 -> NULL
prev curr next
步骤1：反转 current 的指针
NULL <- 1 <- 2 3 -> 4 -> 5 -> NULL
prev curr next
步骤2：继续迭代
NULL <- 1 <- 2 <- 3 4 -> 5 -> NULL
prev curr next
...依此类推
关键步骤：
- 保存
next节点（防止链表断裂） - 反转当前节点的指针：
current->next = prev - 移动指针：
prev和current都向前移动
C++ 实现
class Solution {
public:
// 方法一：迭代法
ListNode* reverseList(ListNode* head) {
ListNode* prev = nullptr;
ListNode* current = head;
while (current != nullptr) {
ListNode* next = current->next; // 1. 保存下一个节点
current->next = prev; // 2. 反转当前节点的指针
prev = current; // 3. prev 向前移动
current = next; // 4. current 向前移动
}
return prev; // prev 是新的头节点
}
// 方法二：递归法
ListNode* reverseList_Recursive(ListNode* head) {
// 基本情况：空链表或只有一个节点
if (head == nullptr || head->next == nullptr) {
return head;
}
// 递归反转后面的链表
ListNode* newHead = reverseList_Recursive(head->next);
// 将当前节点接到反转后的链表末尾
// head->next 现在指向原来的下一个节点
// 让它的 next 指向 head（反转）
head->next->next = head;
head->next = nullptr;
return newHead;
}
};
复杂度分析：
- 时间复杂度：O(n)
- 空间复杂度：O(1) 迭代法，O(n) 递归法（递归栈）
二、合并两个有序链表
LeetCode 21. 合并两个有序链表
题目描述
将两个升序链表合并为一个新的升序链表并返回。新链表通过拼接给定的两个链表的所有节点组成。
示例：
输入：l1 = 1->2->4, l2 = 1->3->4
输出：1->1->2->3->4->4
解题思路
方法一：迭代法
核心思想：
- 使用哑节点简化操作
- 比较两个链表的当前节点
- 将较小的节点接到结果链表
- 最后处理剩余的节点
类比归并排序的合并过程：
就像合并两个有序数组，每次选择较小的元素。
图解：
l1: 1 -> 2 -> 4
l2: 1 -> 3 -> 4
步骤1: 比较 1 和 1，选 l1 的 1
dummy -> 1
↑
current
步骤2: 比较 2 和 1，选 l2 的 1
dummy -> 1 -> 1
↑
current
步骤3: 比较 2 和 3，选 l1 的 2
dummy -> 1 -> 1 -> 2
↑
current
...以此类推
C++ 实现
class Solution {
public:
// 方法一：迭代法（推荐）
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
// 使用哑节点简化操作
ListNode* dummy = new ListNode(0);
ListNode* current = dummy;
// 比较两个链表的节点，选择较小的
while (l1 != nullptr && l2 != nullptr) {
if (l1->val <= l2->val) {
current->next = l1;
l1 = l1->next;
} else {
current->next = l2;
l2 = l2->next;
}
current = current->next;
}
// 连接剩余部分
current->next = (l1 != nullptr) ? l1 : l2;
ListNode* result = dummy->next;
delete dummy;
dummy = nullptr;
return result;
}
// 方法二：递归法
ListNode* mergeTwoLists_Recursive(ListNode* l1, ListNode* l2) {
// 基本情况
if (l1 == nullptr) return l2;
if (l2 == nullptr) return l1;
// 递归合并
if (l1->val <= l2->val) {
l1->next = mergeTwoLists_Recursive(l1->next, l2);
return l1;
} else {
l2->next = mergeTwoLists_Recursive(l1, l2->next);
return l2;
}
}
// 方法三：原地合并（不使用额外节点）
ListNode* mergeTwoLists_InPlace(ListNode* l1, ListNode* l2) {
if (l1 == nullptr) return l2;
if (l2 == nullptr) return l1;
// 确定头节点
ListNode* head = (l1->val <= l2->val) ? l1 : l2;
ListNode* current = head;
if (head == l1) {
l1 = l1->next;
} else {
l2 = l2->next;
}
// 合并
while (l1 != nullptr && l2 != nullptr) {
if (l1->val <= l2->val) {
current->next = l1;
l1 = l1->next;
} else {
current->next = l2;
l2 = l2->next;
}
current = current->next;
}
current->next = (l1 != nullptr) ? l1 : l2;
return head;
}
};
复杂度分析：
- 迭代法：
- 时间复杂度：O(m + n)
- 空间复杂度：O(1)
- 递归法：
- 时间复杂度：O(m + n)
- 空间复杂度：O(m + n)（递归栈）
三、链表的中间节点
LeetCode 876. 链表的中间节点
题目描述
给定一个非空单链表head，返回链表的中间节点。如果有两个中间节点，返回第二个中间节点。
示例：
输入：1->2->3->4->5
输出：3->4->5
输入：1->2->3->4->5->6
输出：4->5->6
解题思路
方法：快慢指针
核心原理：
- 慢指针每次走 1 步
- 快指针每次走 2 步
- 当快指针到达末尾时，慢指针恰好在中间
为什么可行？
- 快指针速度是慢指针的 2 倍
- 当快指针走完全程，慢指针走了一半
- 慢指针的位置就是中间节点
两种情况：
- 奇数个节点：
fast->next == nullptr时停止 - 偶数个节点：
fast == nullptr时停止
图解：
奇数个节点（5个）：
1 -> 2 -> 3 -> 4 -> 5 -> NULL
↑
slow
↑
fast
1 -> 2 -> 3 -> 4 -> 5 -> NULL
↑ ↑
slow fast
1 -> 2 -> 3 -> 4 -> 5 -> NULL
↑ ↑
slow fast
偶数个节点（6个）：
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULL
↑
slow
↑
fast
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULL
↑ ↑
slow fast
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULL
↑ ↑
slow fast
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULL
↑ ↑
slow fast
C++ 实现
class Solution {
public:
// 快慢指针法
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;
}
// 方法二：数组法（不推荐，仅作参考）
ListNode* middleNode_Array(ListNode* head) {
vector<ListNode*> nodes;
ListNode* current = head;
while (current != nullptr) {
nodes.push_back(current);
current = current->next;
}
return nodes[nodes.size() / 2];
}
// 方法三：两次遍历
ListNode* middleNode_TwoPass(ListNode* head) {
// 计算长度
int length = 0;
ListNode* current = head;
while (current != nullptr) {
length++;
current = current->next;
}
// 走到中间
current = head;
for (int i = 0; i < length / 2; i++) {
current = current->next;
}
return current;
}
};
复杂度分析：
- 时间复杂度：O(n)
- 空间复杂度：O(1)
四、判断链表是否有环
LeetCode 141. 环形链表
题目描述
给你一个链表的头节点 head ，判断链表中是否有环。
解题思路
方法：快慢指针（Floyd 判圈算法）
核心原理：
- 慢指针：每次走 1 步
- 快指针：每次走 2 步
- 如果有环，快指针最终会追上慢指针
- 如果无环，快指针会先到达
nullptr
为什么快指针一定能追上慢指针？
想象在环形跑道上：
- 快的人速度是慢的人的 2 倍
- 当慢的人进入环后，快的人也在环中
- 快的人每次相对于慢的人接近 1 步
- 因此必然会相遇
数学证明：
设环的长度为 L，当慢指针进入环时，快指针在环中的位置距离慢指针为 d（0 ≤ d < L）。
每次迭代，快指针相对慢指针前进 1 步，经过 L – d 次迭代后，快指针会追上慢指针（L-d 次迭代也就是说慢指针还没走完一圈就会被快指针追赶上）。
C++ 实现
class Solution {
public:
// 方法一：快慢指针
bool hasCycle(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return false;
}
ListNode* slow = head;
ListNode* fast = head;
while (fast != nullptr && fast->next != nullptr) {
slow = slow->next; // 慢指针走 1 步
fast = fast->next->next; // 快指针走 2 步
if (slow == fast) {
// 相遇，说明有环
return true;
}
}
return false; // 快指针到达末尾，无环
}
// 方法二：哈希表法（空间换时间）
bool hasCycle_Hash(ListNode* head) {
unordered_set<ListNode*> visited;
ListNode* current = head;
while (current != nullptr) {
if (visited.count(current)) {
return true; // 节点已访问过，有环
}
visited.insert(current);
current = current->next;
}
return false;
}
};
复杂度分析：
- 快慢指针法：
- 时间复杂度：O(n)
- 空间复杂度：O(1)
- 哈希表法：
- 时间复杂度：O(n)
- 空间复杂度：O(n)
五、删除链表的倒数第 N 个节点
LeetCode 19. 删除链表的倒数第 N 个节点
题目描述
给定一个链表，删除链表的倒数第 n 个节点，并返回链表的头节点。
示例：
输入：head = 1->2->3->4->5, n = 2
输出：1->2->3->5
解题思路
方法：双指针（一次遍历）
核心思想：
- 使用两个指针，
fast和slow fast先走n+1步- 然后
fast和slow同时移动 - 当
fast到达末尾时，slow指向倒数第n+1个节点 - 删除
slow的下一个节点即可
为什么 fast 要先走 n+1 步？
因为我们需要 slow 停在倒数第 n+1 个节点，这样才能删除倒数第 n 个节点。
图解：
删除倒数第 2 个节点：
dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> NULL
↑
slow
↑
fast
fast 先走 3 步（n+1 = 2+1 = 3）
dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> NULL
↑ ↑
slow fast
同时移动到 fast 为 NULL
dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> NULL
↑ ↑
slow fast
此时 slow.next 就是要删除的节点
使用哑节点的好处：
- 统一处理删除头节点的情况
- 简化边界条件
C++ 实现
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
// 使用哑节点简化边界情况处理
ListNode* dummy = new ListNode(0);
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;
}
// 删除倒数第 n 个节点
ListNode* toDelete = slow->next;
slow->next = slow->next->next;
delete toDelete;
toDelete = nullptr;
ListNode* result = dummy->next;
delete dummy;
dummy = nullptr;
return result;
}
// 方法二：两次遍历
ListNode* removeNthFromEnd_TwoPass(ListNode* head, int n) {
// 计算链表长度
int length = 0;
ListNode* current = head;
while (current != nullptr) {
length++;
current = current->next;
}
// 删除第 length - n + 1 个节点（从前往后数）
ListNode* dummy = new ListNode(0);
dummy->next = head;
current = dummy;
for (int i = 0; i < length - n; i++) {
current = current->next;
}
ListNode* toDelete = current->next;
current->next = current->next->next;
delete toDelete;
ListNode* result = dummy->next;
delete dummy;
return result;
}
};
复杂度分析：
- 时间复杂度：O(n)，一次遍历
- 空间复杂度：O(1)
六、反转链表 II
LeetCode 92. 反转链表 II
题目描述
给你单链表的头指针head和两个整数left和right，其中left ≤ right。请你反转从位置left到位置right的链表节点，返回反转后的链表（仅反转指定区间，不改变其他节点顺序）。
示例：
输入: head = 1->2->3->4->5->NULL, left = 2, right = 4
输出: 1->4->3->2->5->NULL
解题思路
这道题比反转整个链表复杂，需要：
- 找到反转区间的前一个节点
- 反转区间内的节点
- 重新连接三段链表
关键点：
- 使用哑节点（dummy node）简化边界处理
- 定位到
left的前驱节点 - 只反转
left到right区间 - 连接三段：前段 -> 反转段 -> 后段
图解：
原链表: dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> NULL
prev left right succ
反转后: dummy -> 1 -> 4 -> 3 -> 2 -> 5 -> NULL
prev 反转后的区间
C++ 实现
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int left, int right) {
// 使用哑节点简化边界情况
ListNode* dummy = new ListNode(0);
dummy->next = head;
// 1. 找到 left 的前驱节点
ListNode* prev = dummy;
for (int i = 1; i < left; i++) {
prev = prev->next;
}
// 2. 开始反转
ListNode* current = prev->next; // left 节点
// 头插法：将 current 后面的节点依次插入到 prev 后面
for (int i = 0; i < right - left; i++) {
ListNode* next = current->next;
current->next = next->next;
next->next = prev->next;
prev->next = next;
}
ListNode* result = dummy->next;
delete dummy;
return result;
}
// 方法二：穿针引线法（更容易理解）
ListNode* reverseBetween_v2(ListNode* head, int left, int right) {
ListNode* dummy = new ListNode(0);
dummy->next = head;
ListNode* pre = dummy;
// 找到 left 的前驱节点
for (int i = 1; i < left; i++) {
pre = pre->next;
}
// 反转 left 到 right 区间
ListNode* leftNode = pre->next;
ListNode* rightNode = leftNode;
for (int i = 0; i < right - left; i++) {
rightNode = rightNode->next;
}
// 记录后继节点
ListNode* succ = rightNode->next;
// 切断链接
pre->next = nullptr;
rightNode->next = nullptr;
// 反转
reverseLinkedList(leftNode);
// 重新连接
pre->next = rightNode;
leftNode->next = succ;
ListNode* result = dummy->next;
delete dummy;
dummy = nullptr;
return result;
}
private:
void reverseLinkedList(ListNode* head) {
ListNode* prev = nullptr;
ListNode* current = head;
while (current != nullptr) {
ListNode* next = current->next;
current->next = prev;
prev = current;
current = next;
}
}
};
复杂度分析：
- 时间复杂度：O(n)
- 空间复杂度：O(1)
七、环形链表 II – 找环的入口
LeetCode 142. 环形链表 II
题目描述
给定一个链表的头节点 head，如果有环，返回链表开始入环的第一个节点；如果没有环，返回 null。
解题思路
这是环形链表的进阶版，需要找到环的入口。
数学推导：
设：
- 链表头到环入口距离为
a - 环入口到相遇点距离为
b - 相遇点到环入口距离为
c - 环的长度为
b + c
第一步：快慢指针相遇
当快慢指针相遇时：
- 慢指针走过的距离：
a + b - 快指针走过的距离：
a + b + n(b + c)（n 为快指针在环中多走的圈数）
因为快指针速度是慢指针的 2 倍：
2(a + b) = a + b + n(b + c)
a + b = n(b + c)
a = n(b + c) - b
a = (n-1)(b + c) + c
关键结论：
从头节点到环入口的距离 = 从相遇点绕环到环入口的距离
第二步：找环入口
让一个指针从头开始，另一个指针从相遇点开始，两者以相同速度前进，它们会在环入口相遇。
图解：
链表: 1 -> 2 -> 3 -> 4 -> 5
↑ ↓
8 6
↑ ↓
<- 7 <-
a = 3 (1->2->3)
b = 5 (3->4->5->6->7)
c = 3 (7->8->3)
相遇点在节点 7
从头节点走 3 步到达节点 3（环入口）
从节点 7 走 3 步也到达节点 3（7->8->3）
C++ 实现
class Solution {
public:
ListNode* detectCycle(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return nullptr;
}
ListNode* slow = head;
ListNode* fast = head;
// 第一步：判断是否有环，找到相遇点
while (fast != nullptr && fast->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
// 有环
// 第二步：找环的入口
ListNode* ptr = head;
while (ptr != slow) {
ptr = ptr->next;
slow = slow->next;
}
return ptr; // 环的入口
}
}
return nullptr; // 无环
}
// 哈希表法（更直观）
ListNode* detectCycle_Hash(ListNode* head) {
unordered_set<ListNode*> visited;
ListNode* current = head;
while (current != nullptr) {
if (visited.count(current)) {
return current; // 第一个重复访问的节点就是环入口
}
visited.insert(current);
current = current->next;
}
return nullptr;
}
};
复杂度分析：
- 快慢指针法：
- 时间复杂度：O(n)
- 空间复杂度：O(1)
- 哈希表法：
- 时间复杂度：O(n)
- 空间复杂度：O(n)
八、判断两个链表是否相交
LeetCode 160. 相交链表
题目描述
给定两个单链表的头节点 headA 和 headB，找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null。
注意：相交是指节点引用相同，而不是值相同。
解题思路
方法一：双指针法（最优解）
让两个指针分别遍历两个链表，当一个指针到达末尾时，切换到另一个链表的头部继续遍历。如果相交，两个指针最终会在交点相遇；如果不相交，最终都变为 null。
核心思想：消除两个链表的长度差
设链表 A 长度为 a + c，链表 B 长度为 b + c，其中 c 是公共部分的长度。
巧妙之处：
- 指针 pA 先遍历链表 A，再遍历链表 B，总路程：
a + c + b - 指针 pB 先遍历链表 B，再遍历链表 A，总路程：
b + c + a - 两个指针走的总距离相同！
三种情况：
- 有交点：两指针会在交点相遇
- 无交点：两指针会同时到达末尾（都为
nullptr） - 其中一个为空：直接返回
nullptr
图解：
链表 A: a1 -> a2 -> c1 -> c2 -> c3
链表 B: b1 -> b2 -> b3 -> c1 -> c2 -> c3
pA 路径: a1 -> a2 -> c1 -> c2 -> c3 -> b1 -> b2 -> b3 -> c1 (相遇)
pB 路径: b1 -> b2 -> b3 -> c1 -> c2 -> c3 -> a1 -> a2 -> c1 (相遇)
C++ 实现
class Solution {
public:
// 方法一：双指针法（推荐）
ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
if (headA == nullptr || headB == nullptr) {
return nullptr;
}
ListNode* pA = headA;
ListNode* pB = headB;
// 当两个指针相遇时，要么在交点，要么都是 nullptr
while (pA != pB) {
// pA 遍历完 A 后遍历 B
pA = (pA == nullptr) ? headB : pA->next;
// pB 遍历完 B 后遍历 A
pB = (pB == nullptr) ? headA : pB->next;
}
return pA; // 交点或 nullptr
}
// 方法二：哈希表法
ListNode* getIntersectionNode_Hash(ListNode* headA, ListNode* headB) {
unordered_set<ListNode*> visited;
// 将链表 A 的所有节点加入哈希表
ListNode* current = headA;
while (current != nullptr) {
visited.insert(current);
current = current->next;
}
// 遍历链表 B，查找第一个在哈希表中的节点
current = headB;
while (current != nullptr) {
if (visited.count(current)) {
return current; // 找到交点
}
current = current->next;
}
return nullptr; // 不相交
}
// 方法三：长度差法
ListNode* getIntersectionNode_Length(ListNode* headA, ListNode* headB) {
// 计算两个链表的长度
int lenA = getLength(headA);
int lenB = getLength(headB);
// 让长的链表先走差值步
while (lenA > lenB) {
headA = headA->next;
lenA--;
}
while (lenB > lenA) {
headB = headB->next;
lenB--;
}
// 同时前进，找到相交点
while (headA != headB) {
headA = headA->next;
headB = headB->next;
}
return headA;
}
private:
int getLength(ListNode* head) {
int length = 0;
while (head != nullptr) {
length++;
head = head->next;
}
return length;
}
};
复杂度分析：
- 双指针法：
- 时间复杂度：O(m + n)
- 空间复杂度：O(1) ⭐ 最优
- 哈希表法：
- 时间复杂度：O(m + n)
- 空间复杂度：O(m) 或 O(n)
九、回文链表
LeetCode 234. 回文链表
题目描述
判断一个链表是否为回文链表。
示例：
输入: 1->2->2->1
输出: true
输入: 1->2
输出: false
解题思路
方法一：反转后半部分链表（最优解）
核心步骤：
- 使用快慢指针找到链表的中间节点
- 反转后半部分链表
- 比较前半部分和反转后的后半部分
- （可选）恢复链表
为什么要找中间节点？
回文的特点是前半部分和后半部分对称，所以我们只需要比较这两部分。
图解：
原链表: 1 -> 2 -> 3 -> 2 -> 1
步骤1：找中间节点
1 -> 2 -> 3 -> 2 -> 1
↑
中间
步骤2：反转后半部分
前半: 1 -> 2 -> 3
后半: 1 -> 2（已反转）
步骤3：比较
1 == 1
2 == 2
结果: true
处理奇偶长度：
- 奇数长度：中间节点不参与比较
- 偶数长度：分成两个相等的部分
C++ 实现
class Solution {
public:
// 方法一：反转后半部分（推荐）
bool isPalindrome(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return true;
}
// 1. 找到中间节点
ListNode* slow = head;
ListNode* fast = head;
while (fast->next != nullptr && fast->next->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
}
// 2. 反转后半部分
ListNode* secondHalf = reverseList(slow->next);
// 3. 比较两部分
ListNode* p1 = head;
ListNode* p2 = secondHalf;
bool result = true;
while (p2 != nullptr) {
// 只需遍历后半部分
if (p1->val != p2->val) {
result = false;
break;
}
p1 = p1->next;
p2 = p2->next;
}
// 4. 恢复链表（可选）
slow->next = reverseList(secondHalf);
return result;
}
// 方法二：使用栈（空间换时间）
bool isPalindrome_Stack(ListNode* head) {
stack<int> s;
ListNode* current = head;
// 将所有值压入栈
while (current != nullptr) {
s.push(current->val);
current = current->next;
}
// 从头遍历，同时从栈顶取值比较
current = head;
while (current != nullptr) {
if (current->val != s.top()) {
return false;
}
s.pop();
current = current->next;
}
return true;
}
// 方法三：递归法
ListNode* frontPointer;
bool isPalindrome_Recursive(ListNode* head) {
frontPointer = head;
return recursivelyCheck(head);
}
private:
ListNode* reverseList(ListNode* head) {
ListNode* prev = nullptr;
ListNode* current = head;
while (current != nullptr) {
ListNode* next = current->next;
current->next = prev;
prev = current;
current = next;
}
return prev;
}
bool recursivelyCheck(ListNode* currentNode) {
if (currentNode != nullptr) {
if (!recursivelyCheck(currentNode->next)) {
return false;
}
if (currentNode->val != frontPointer->val) {
return false;
}
frontPointer = frontPointer->next;
}
return true;
}
};
复杂度分析：
- 反转后半部分：
- 时间复杂度：O(n)
- 空间复杂度：O(1) ⭐ 最优
- 栈法：
- 时间复杂度：O(n)
- 空间复杂度：O(n)
总结
核心技巧汇总
| 技巧 | 适用题目 | 原理 |
|---|---|---|
| 快慢指针 | 环检测、找中间节点 | 速度差产生相对位移 |
| 双指针 | 链表相交、删除倒数节点 | 消除长度差 |
| 哑节点 | 删除节点、合并链表 | 简化边界处理 |
| 递归 | 反转、合并 | 分治思想 |
| 三指针 | 反转链表 | 保存前驱和后继 |
面试技巧
- 画图辅助思考：链表题一定要画图，能帮助理清思路
- 注意边界条件：
- 空链表
- 单节点链表
- 两节点链表
- 空指针检查：访问
->next之前确保指针非空 - 使用哑节点：涉及头节点操作时，哑节点能大大简化代码
- 时间空间权衡：优先考虑 O(1) 空间复杂度的解法
刷题顺序建议
基础题（必做）：
- 反转链表
- 合并两个有序链表
- 链表的中间节点
进阶题（重点）：
4. 判断链表是否有环
5. 删除链表的倒数第 N 个节点
高级题（拔高）：
6. 反转链表 II
7. 环形链表 II
8. 相交链表
9. 回文链表
掌握这 9 道题，你就能应对大部分链表面试题！记住，链表的本质是指针操作，多画图、多练习，熟能生巧。
附录：测试代码
// 创建链表的辅助函数
ListNode* createList(vector<int>& vals) {
if (vals.empty()) return nullptr;
ListNode* head = new ListNode(vals[0]);
ListNode* current = head;
for (int i = 1; i < vals.size(); i++) {
current->next = new ListNode(vals[i]);
current = current->next;
}
return head;
}
// 打印链表
void printList(ListNode* head) {
while (head != nullptr) {
cout << head->val;
if (head->next != nullptr) cout << " -> ";
head = head->next;
}
cout << endl;
}
// 删除链表
void deleteList(ListNode* head) {
while (head != nullptr) {
ListNode* temp = head;
head = head->next;
delete temp;
}
}
// 测试示例
int main() {
Solution solution;
// 测试反转链表
vector<int> vals = {
1, 2, 3, 4, 5};
ListNode* head = createList(vals);
cout << "原链表: ";
printList(head);
head = solution.reverseList(head);
cout << "反转后: ";
printList(head);
deleteList(head);
return 0;
}
祝你面试顺利！