C算法
链表经典题目实战解析：LeetCode Hot 100 高频题解
链表经典题目实战解析涵盖反转链表、环形链表、合并有序链表及删除倒数第 N 个结点。通过迭代与递归双指针等核心技巧，深入剖析解题思路与代码实现。重点讲解虚拟头节点处理边界条件，快慢指针判断环结构，以及时间空间复杂度分析。旨在巩固链表知识，提升算法思维与面试应对能力。
链表经典题目实战解析涵盖反转链表、环形链表、合并有序链表及删除倒数第 N 个结点。通过迭代与递归双指针等核心技巧，深入剖析解题思路与代码实现。重点讲解虚拟头节点处理边界条件，快慢指针判断环结构，以及时间空间复杂度分析。旨在巩固链表知识，提升算法思维与面试应对能力。
在进入具体题目之前，我们先来回顾一下解决链表问题的几个核心技巧，它们将是你手中最强大的武器：
node.next 也是一个链表）使得递归成为一种优雅的解法，尤其适用于反转、合并等问题。head == NULL、head->next == NULL 等特殊情况。题目描述：给你单链表的头节点 head，请你反转链表，并返回反转后的链表。
示例：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
难度：简单
考察频率：⭐⭐⭐⭐⭐ （面试必考题）
解题思路：
使用两个指针 prev 和 cur。prev 初始为 NULL，cur 初始为 head。在遍历链表时，将 cur 的 next 指针指向 prev，然后 prev 和 cur 同时向后移动。当 cur 为 NULL 时，prev 就是新的头节点。
核心要点：必须提前保存 cur->next，否则反转指针后会丢失后续链表。
代码实现：
struct ListNode* reverseList(struct ListNode* head) {
// 处理空链表和单节点链表
if(head == NULL || head->next == NULL) {
return head;
}
struct ListNode* prev = NULL;
struct ListNode* cur = head;
while(cur != NULL) {
struct ListNode* next = cur->next; // 保存下一个节点，防止链表断裂
cur->next = prev; // 反转当前节点的指针
prev = cur; // prev 指针后移
cur = next; // cur 指针后移
}
return prev; // prev 成为新的头节点
}
复杂度分析：
边界测试用例：
NULL → 输出 NULL[1] → 输出 [1]解题思路： 递归的核心思想是'大事化小'。假设链表的后半部分已经被反转，我们只需要处理当前节点和它后面的节点。
head 为 NULL 或 head->next 为 NULL。reverseList(head->next)，得到反转后的新头节点 newHead。next 指向自己，即 head->next->next = head。next 指向 NULL，防止链表成环。newHead。代码实现：
struct ListNode* reverseList(struct ListNode* head) {
// 递归终止条件：空链表 或 只有一个节点
if(head == NULL || head->next == NULL) {
return head;
}
// 递归调用，反转 head 之后的所有节点
struct ListNode* newHead = reverseList(head->next);
// 反转当前节点与下一个节点的指向
head->next->next = head;
head->next = NULL; // 防止链表成环，这一步是关键
return newHead;
}
复杂度分析：
解法对比：
| 解法 | 优点 | 缺点 |
|---|---|---|
| 迭代 | 空间复杂度低，原地反转 | 思路相对抽象 |
| 递归 | 代码简洁优雅，符合链表特性 | 空间复杂度高，存在栈溢出风险 |
题目描述：给你一个链表的头节点 head，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。
示例：
输入：head = [3,2,0,-4], pos = 1 (链表尾部连接到第二个节点)
输出：true
难度：简单
考察频率：⭐⭐⭐⭐
解题思路： 想象在环形跑道上跑步的场景：一个跑得快的运动员和一个跑得慢的运动员，如果跑道是环形的，快的运动员最终一定会追上慢的运动员；如果是直线跑道，快的运动员会先到达终点。
slow：每次向后移动 1 步。fast：每次向后移动 2 步。fast 指针会追上 slow 指针，此时 slow == fast。fast 指针会先到达链表末尾（fast == NULL 或 fast->next == NULL）。代码实现：
bool hasCycle(struct ListNode* head) {
// 处理空链表和单节点链表
if(head == NULL || head->next == NULL) {
return false;
}
struct ListNode* slow = head;
struct ListNode* fast = head->next; // 初始错开，避免直接相等
while(slow != fast) {
// 快指针到达终点，无环
if(fast == NULL || fast->next == NULL) {
return false;
}
slow = slow->next; // 慢指针走一步
fast = fast->next->next; // 快指针走两步
}
// 快慢指针相遇，有环
return true;
}
关键细节：
head->next，而不是 head，避免循环一开始就满足 slow == fast。fast 和 fast->next 是否为空，防止空指针访问。复杂度分析：
拓展思路：哈希表法 可以使用哈希表存储访问过的节点，遍历链表时如果遇到重复节点则说明有环。但该方法空间复杂度为 O(N)，不如快慢指针法高效。
题目描述：将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
难度：简单
考察频率：⭐⭐⭐⭐⭐
解题思路：
这是一个典型的归并操作。直接操作两个链表的头节点会面临边界问题（比如某个链表为空），因此我们引入虚拟头节点 dummy，用 cur 指针构建新链表。
dummy，cur 指针初始指向 dummy。cur 后面。cur 指针。cur 后面。dummy->next 作为新链表的头节点。代码实现：
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
// 创建虚拟头节点，简化边界处理
struct ListNode dummy;
dummy.next = NULL;
struct ListNode* cur = &dummy;
// 同时遍历两个链表
while(list1 != NULL && list2 != NULL) {
if(list1->val < list2->val) {
cur->next = list1;
list1 = list1->next;
} else {
cur->next = list2;
list2 = list2->next;
}
cur = cur->next; // cur 指针后移
}
// 连接剩余的节点
cur->next = (list1 != NULL) ? list1 : list2;
return dummy.next;
}
复杂度分析：
解题思路： 递归的核心是每次选择两个链表中较小的头节点，然后递归合并剩余的部分。
list1 为空，返回 list2；如果 list2 为空，返回 list1。list1 和 list2 的头节点值，选择较小的作为当前节点。代码实现：
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
// 终止条件：一个链表为空，返回另一个链表
if(list1 == NULL) {
return list2;
}
if(list2 == NULL) {
return list1;
}
// 选择较小的节点作为当前节点
if(list1->val < list2->val) {
list1->next = mergeTwoLists(list1->next, list2);
return list1;
} else {
list2->next = mergeTwoLists(list1, list2->next);
return list2;
}
}
复杂度分析：
题目描述：给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
示例：
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
难度：中等
考察频率：⭐⭐⭐⭐⭐
解题思路：
删除倒数第 n 个节点，关键是找到倒数第 n+1 个节点（目标节点的前驱节点）。使用双指针法可以在一次遍历中完成：
dummy，指向 head，避免删除头节点的边界问题。fast 和 slow，初始都指向 dummy。fast 指针向前移动 n+1 步，使 fast 和 slow 之间间隔 n 个节点。fast 和 slow 同时向前移动，直到 fast 指向 NULL。slow 指向的就是倒数第 n+1 个节点，执行删除操作：slow->next = slow->next->next。dummy->next。代码实现：
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
// 创建虚拟头节点
struct ListNode dummy;
dummy.next = head;
struct ListNode* fast = &dummy;
struct ListNode* slow = &dummy;
// fast 指针先走 n+1 步
for(int i = 0; i <= n; i++) {
fast = fast->next;
}
// 快慢指针同时移动
while(fast != NULL) {
fast = fast->next;
slow = slow->next;
}
// 删除倒数第 n 个节点
struct ListNode* temp = slow->next; // 保存要删除的节点
slow->next = slow->next->next;
free(temp); // 释放内存，避免内存泄漏
return dummy.next;
}
关键细节：
n 等于链表长度时，无法删除头节点。fast 指针需要移动 n+1 步，而不是 n 步，这样才能让 slow 停在目标节点的前驱。复杂度分析：
通过对这四道经典题目的深入剖析，你不仅巩固了链表的基础知识，更重要的是掌握了双指针、虚拟头节点、递归等高级解题技巧，并学会了从不同角度思考问题，分析算法的优劣。
这几道题目只是链表领域的冰山一角，想要成为真正的'链表王者'，还需要攻克以下进阶题目：
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online