【线性表系列终篇】链表试炼：LeetCode Hot 100 经典题目实战解析
🏠个人主页：黎雁
🎬作者简介：C/C++/JAVA后端开发学习者
❄️个人专栏：C语言、数据结构（C语言）、EasyX、游戏、规划、程序人生
✨ 从来绝巘须孤往，万里同尘即玉京
文章目录
【线性表系列终篇】链表试炼：LeetCode Hot 100 经典题目实战解析
你好！欢迎来到线性表系列的终篇。
经过前三篇的系统学习，我们已经从理论到实践，完整地掌握了单向链表和双向带头循环链表的核心知识。从理解“物理连续”到“逻辑连续”的思维转变，到手写代码攻克指针难题，再到领略数据结构设计的优雅哲学，你已经完成了从新手到高手的蜕变。
但真正的试炼，才刚刚开始。
今天，我们将不再局限于基础操作的实现，而是将目光投向LeetCode Hot 100中的链表经典题目。这些题目是检验你对链表理解深度、算法思维和编码能力的试金石，也是面试中高频出现的“拦路虎”。
准备好了吗？让我们戴上“链表王者”的桂冠，迎接最终的试炼！⚔️
文章摘要
本文为线性表系列终篇，聚焦LeetCode Hot 100中的链表经典题目实战解析。针对反转链表、环形链表、合并有序链表、删除链表倒数第N个节点等高频考点，深入剖析解题思路，提供迭代、递归等多种高效解法，结合代码实现与复杂度分析，补充边界条件处理技巧，帮助读者巩固链表知识，提升算法思维与编码能力，从容应对面试挑战。
阅读时长：约30分钟
阅读建议：
- 初学者：先尝试独立解题，再对照解析，重点理解解题思路
- 进阶者：对比不同解法的优劣，思考优化空间
- 面试者：重点掌握代码实现细节与复杂度分析，模拟面试场景
- 查漏补缺者：针对薄弱题型，反复练习，总结规律
一、试炼前的准备：链表解题核心技巧回顾
【线性表系列入门篇】从顺序表到链表：解锁数据结构的进化密码
【线性表系列进阶篇】手搓单向链表：从指针迷宫到代码实现
【线性表系列高阶篇】双向带头循环链表：结构王者的极致优雅实现
在进入具体题目之前，我们先来回顾一下解决链表问题的几个核心技巧，它们将是你手中最强大的武器：
- 双指针法 (Two Pointers)：这是链表问题中最常用、最高效的技巧。通过设置快慢指针、前后指针、间隔指针等，可以解决很多看似复杂的问题，如找中点、判断环、删除倒数第N个节点等。
- 虚拟头节点 (Dummy Head Node)：类似于我们实现的双向链表的哨兵位，它可以完美解决头节点可能被删除的边界问题，让代码逻辑更加统一和简洁。
- 递归 (Recursion)：链表的天然递归结构（
node.next也是一个链表）使得递归成为一种优雅的解法，尤其适用于反转、合并等问题。 - 画图辅助 (Draw a Picture)：当指针关系变得复杂时，动手在纸上画出节点和指针的指向变化，是理清思路、避免错误的最佳方法。
- 边界条件优先处理：链表类题目最容易出错的地方就是边界，解题时优先处理
head == NULL、head->next == NULL等特殊情况。
二、试炼开始：经典题目实战解析
题目一：反转链表 (LeetCode 206)
题目描述：给你单链表的头节点 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，否则反转指针后会丢失后续链表。
代码实现：
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */structListNode*reverseList(structListNode* head){// 处理空链表和单节点链表if(head ==NULL|| head->next ==NULL){return head;}structListNode* prev =NULL;structListNode* cur = head;while(cur !=NULL){structListNode* next = cur->next;// 保存下一个节点，防止链表断裂 cur->next = prev;// 反转当前节点的指针 prev = cur;// prev 指针后移 cur = next;// cur 指针后移}return prev;// prev 成为新的头节点}复杂度分析：
- 时间复杂度：O(N)，其中 N 是链表的长度。需要遍历链表一次。
- 空间复杂度：O(1)，只使用了几个指针变量，属于原地反转。
边界测试用例：
- 输入
NULL→ 输出NULL - 输入
[1]→ 输出[1]
解法二：递归
解题思路：
递归的核心思想是“大事化小”。假设链表的后半部分已经被反转，我们只需要处理当前节点和它后面的节点。
- 递归终止条件：
head为NULL或head->next为NULL。 - 递归调用
reverseList(head->next)，得到反转后的新头节点newHead。 - 将当前节点的下一个节点的
next指向自己，即head->next->next = head。 - 将当前节点的
next指向NULL，防止链表成环。 - 返回新头节点
newHead。
代码实现：
structListNode*reverseList(structListNode* head){// 递归终止条件：空链表 或 只有一个节点if(head ==NULL|| head->next ==NULL){return head;}// 递归调用，反转 head 之后的所有节点structListNode* newHead =reverseList(head->next);// 反转当前节点与下一个节点的指向 head->next->next = head; head->next =NULL;// 防止链表成环，这一步是关键return newHead;}复杂度分析：
- 时间复杂度：O(N)，需要递归 N 次，遍历所有节点。
- 空间复杂度：O(N)，递归调用栈的深度为 N，最坏情况下链表退化为一条链。
解法对比：
| 解法 | 优点 | 缺点 |
|---|---|---|
| 迭代 | 空间复杂度低，原地反转 | 思路相对抽象 |
| 递归 | 代码简洁优雅，符合链表特性 | 空间复杂度高，存在栈溢出风险 |
题目二：环形链表 (LeetCode 141)
题目描述：给你一个链表的头节点 head，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。
示例：
输入：head = [3,2,0,-4], pos = 1 (链表尾部连接到第二个节点)
输出：true
难度：简单
考察频率：⭐⭐⭐⭐
解法：快慢指针（Floyd判圈算法）
解题思路：
想象在环形跑道上跑步的场景：一个跑得快的运动员和一个跑得慢的运动员，如果跑道是环形的，快的运动员最终一定会追上慢的运动员；如果是直线跑道，快的运动员会先到达终点。
- 设置慢指针
slow：每次向后移动 1 步。 - 设置快指针
fast：每次向后移动 2 步。 - 有环情况：
fast指针会追上slow指针，此时slow == fast。 - 无环情况：
fast指针会先到达链表末尾（fast == NULL或fast->next == NULL）。
代码实现：
bool hasCycle(structListNode*head){// 处理空链表和单节点链表if(head ==NULL|| head->next ==NULL){return false;}structListNode* slow = head;structListNode* 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)。有环时，快慢指针相遇时，慢指针走过的距离不会超过链表总长度；无环时，快指针遍历链表一次。
- 空间复杂度：O(1)，只使用了两个指针变量，无需额外空间。
拓展思路：哈希表法
可以使用哈希表存储访问过的节点，遍历链表时如果遇到重复节点则说明有环。但该方法空间复杂度为 O(N)，不如快慢指针法高效。
题目三：合并两个有序链表 (LeetCode 21)
题目描述：将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
难度：简单
考察频率：⭐⭐⭐⭐⭐
解法一：迭代（虚拟头节点）
解题思路：
这是一个典型的归并操作。直接操作两个链表的头节点会面临边界问题（比如某个链表为空），因此我们引入虚拟头节点 dummy，用 cur 指针构建新链表。
- 创建虚拟头节点
dummy，cur指针初始指向dummy。 - 循环比较两个链表的当前节点值，将较小值的节点连接到
cur后面。 - 移动对应链表的指针和
cur指针。 - 当其中一个链表遍历完后，将另一个链表的剩余部分直接连接到
cur后面。 - 返回
dummy->next作为新链表的头节点。
代码实现：
structListNode*mergeTwoLists(structListNode* list1,structListNode* list2){// 创建虚拟头节点，简化边界处理structListNode dummy; dummy.next =NULL;structListNode* 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;}复杂度分析：
- 时间复杂度：O(N + M)，其中 N 和 M 分别是两个链表的长度，需要遍历所有节点。
- 空间复杂度：O(1)，只使用了虚拟头节点和几个指针，原地合并。
解法二：递归
解题思路：
递归的核心是每次选择两个链表中较小的头节点，然后递归合并剩余的部分。
- 终止条件：如果
list1为空，返回list2；如果list2为空，返回list1。 - 比较
list1和list2的头节点值，选择较小的作为当前节点。 - 递归合并剩余的链表，并将结果连接到当前节点的后面。
- 返回当前节点。
代码实现：
structListNode*mergeTwoLists(structListNode* list1,structListNode* 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;}}复杂度分析：
- 时间复杂度：O(N + M)，需要递归合并所有节点。
- 空间复杂度：O(N + M)，递归调用栈的深度为两个链表的长度之和。
题目四：删除链表的倒数第 N 个结点 (LeetCode 19)
题目描述：给你一个链表，删除链表的倒数第 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。
代码实现：
structListNode*removeNthFromEnd(structListNode* head,int n){// 创建虚拟头节点structListNode dummy; dummy.next = head;structListNode* fast =&dummy;structListNode* 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 个节点structListNode* temp = slow->next;// 保存要删除的节点 slow->next = slow->next->next;free(temp);// 释放内存，避免内存泄漏return dummy.next;}关键细节：
- 虚拟头节点是必须的，否则当
n等于链表长度时，无法删除头节点。 fast指针需要移动n+1步，而不是n步，这样才能让slow停在目标节点的前驱。- 删除节点后要释放内存，避免内存泄漏。
复杂度分析：
- 时间复杂度：O(N)，只需要遍历链表一次。
- 空间复杂度：O(1)，使用常数级别的额外空间。
三、试炼总结与后续挑战
恭喜你完成了本次链表王者试炼！通过对这四道经典题目的深入剖析，你不仅巩固了链表的基础知识，更重要的是掌握了双指针、虚拟头节点、递归等高级解题技巧，并学会了从不同角度思考问题，分析算法的优劣。
你已掌握的核心能力
- 算法思维：能够分析问题本质，选择最优的解题策略。
- 编码能力：能够将解题思路转化为清晰、高效、健壮的代码。
- 复杂度分析：能够评估算法的时间和空间效率，选择最优解。
- 边界处理：能够考虑到各种特殊情况，写出鲁棒性强的代码。
后续挑战（LeetCode Hot 100 链表高频题）
这几道题目只是链表领域的冰山一角，想要成为真正的“链表王者”，还需要攻克以下进阶题目：
- K 个一组翻转链表 (LeetCode 25)：反转链表的进阶版，难度较大，面试高频硬核题。
- 相交链表 (LeetCode 160)：寻找两个链表的第一个公共节点，双指针法的巧妙应用。
- 复制带随机指针的链表 (LeetCode 138)：对链表和哈希表的综合考察，难度较高。
- 排序链表 (LeetCode 148)：要求 O(n log n) 时间复杂度和常数级空间复杂度，考验算法功底。
四、线性表系列全回顾
从顺序表到单向链表，再到双向带头循环链表，最后到算法实战，我们的线性表系列已经圆满结束：
- 入门篇：剖析顺序表缺陷，引出链表的核心设计思想。
- 进阶篇：手撸单向不带头非循环链表，攻克指针和二级指针难点。
- 高阶篇：实现双向带头循环链表，领略数据结构设计的优雅。
- 终篇：实战 LeetCode 经典题目，将理论转化为解题能力。
数据结构与算法的学习之路永无止境，没有捷径可走，唯有多敲代码、多画图、多思考，才能真正掌握其精髓。希望这个系列能成为你坚实的基石，祝你在未来的学习和面试中披荆斩棘，所向披靡！🚀
点赞+收藏+关注，感谢一路以来的支持！我们下一个系列再见！👋
