【线性表系列终篇】链表试炼：LeetCode Hot 100 经典题目实战解析

Ne0inhk

— 15 min read
【线性表系列终篇】链表试炼：LeetCode Hot 100 经典题目实战解析
在这里插入图片描述
🏠个人主页：黎雁
🎬作者简介：C/C++/JAVA后端开发学习者
❄️个人专栏：C语言、数据结构（C语言）、EasyX、游戏、规划、程序人生
✨ 从来绝巘须孤往，万里同尘即玉京
在这里插入图片描述

文章目录

【线性表系列终篇】链表试炼：LeetCode Hot 100 经典题目实战解析

你好！欢迎来到线性表系列的终篇。

经过前三篇的系统学习，我们已经从理论到实践，完整地掌握了单向链表和双向带头循环链表的核心知识。从理解“物理连续”到“逻辑连续”的思维转变，到手写代码攻克指针难题，再到领略数据结构设计的优雅哲学，你已经完成了从新手到高手的蜕变。

但真正的试炼，才刚刚开始。

今天，我们将不再局限于基础操作的实现，而是将目光投向LeetCode Hot 100中的链表经典题目。这些题目是检验你对链表理解深度、算法思维和编码能力的试金石，也是面试中高频出现的“拦路虎”。

准备好了吗？让我们戴上“链表王者”的桂冠，迎接最终的试炼！⚔️

文章摘要

本文为线性表系列终篇，聚焦LeetCode Hot 100中的链表经典题目实战解析。针对反转链表、环形链表、合并有序链表、删除链表倒数第N个节点等高频考点，深入剖析解题思路，提供迭代、递归等多种高效解法，结合代码实现与复杂度分析，补充边界条件处理技巧，帮助读者巩固链表知识，提升算法思维与编码能力，从容应对面试挑战。

阅读时长：约30分钟
阅读建议：

  1. 初学者：先尝试独立解题，再对照解析，重点理解解题思路
  2. 进阶者：对比不同解法的优劣，思考优化空间
  3. 面试者：重点掌握代码实现细节与复杂度分析，模拟面试场景
  4. 查漏补缺者：针对薄弱题型，反复练习，总结规律

一、试炼前的准备：链表解题核心技巧回顾

【线性表系列入门篇】从顺序表到链表：解锁数据结构的进化密码
【线性表系列进阶篇】手搓单向链表：从指针迷宫到代码实现
【线性表系列高阶篇】双向带头循环链表：结构王者的极致优雅实现

在进入具体题目之前，我们先来回顾一下解决链表问题的几个核心技巧，它们将是你手中最强大的武器：

  1. 双指针法 (Two Pointers)：这是链表问题中最常用、最高效的技巧。通过设置快慢指针、前后指针、间隔指针等，可以解决很多看似复杂的问题，如找中点、判断环、删除倒数第N个节点等。
  2. 虚拟头节点 (Dummy Head Node)：类似于我们实现的双向链表的哨兵位，它可以完美解决头节点可能被删除的边界问题，让代码逻辑更加统一和简洁。
  3. 递归 (Recursion)：链表的天然递归结构（node.next 也是一个链表）使得递归成为一种优雅的解法，尤其适用于反转、合并等问题。
  4. 画图辅助 (Draw a Picture)：当指针关系变得复杂时，动手在纸上画出节点和指针的指向变化，是理清思路、避免错误的最佳方法。
  5. 边界条件优先处理：链表类题目最容易出错的地方就是边界，解题时优先处理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]
解法二：递归

解题思路：
递归的核心思想是“大事化小”。假设链表的后半部分已经被反转，我们只需要处理当前节点和它后面的节点。

  1. 递归终止条件：head 为 NULL 或 head->next 为 NULL。
  2. 递归调用 reverseList(head->next)，得到反转后的新头节点 newHead。
  3. 将当前节点的下一个节点的 next 指向自己，即 head->next->next = head。
  4. 将当前节点的 next 指向 NULL，防止链表成环。
  5. 返回新头节点 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 指针构建新链表。

  1. 创建虚拟头节点 dummy，cur 指针初始指向 dummy。
  2. 循环比较两个链表的当前节点值，将较小值的节点连接到 cur 后面。
  3. 移动对应链表的指针和 cur 指针。
  4. 当其中一个链表遍历完后，将另一个链表的剩余部分直接连接到 cur 后面。
  5. 返回 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)，只使用了虚拟头节点和几个指针，原地合并。
解法二：递归

解题思路：
递归的核心是每次选择两个链表中较小的头节点，然后递归合并剩余的部分。

  1. 终止条件：如果 list1 为空，返回 list2；如果 list2 为空，返回 list1。
  2. 比较 list1 和 list2 的头节点值，选择较小的作为当前节点。
  3. 递归合并剩余的链表，并将结果连接到当前节点的后面。
  4. 返回当前节点。

代码实现：

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 个节点（目标节点的前驱节点）。使用双指针法可以在一次遍历中完成：

  1. 创建虚拟头节点 dummy，指向 head，避免删除头节点的边界问题。
  2. 定义快慢指针 fast 和 slow，初始都指向 dummy。
  3. 先让 fast 指针向前移动 n+1 步，使 fast 和 slow 之间间隔 n 个节点。
  4. 然后让 fast 和 slow 同时向前移动，直到 fast 指向 NULL。
  5. 此时 slow 指向的就是倒数第 n+1 个节点，执行删除操作：slow->next = slow->next->next。
  6. 返回 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)，使用常数级别的额外空间。

三、试炼总结与后续挑战

恭喜你完成了本次链表王者试炼！通过对这四道经典题目的深入剖析，你不仅巩固了链表的基础知识，更重要的是掌握了双指针、虚拟头节点、递归等高级解题技巧，并学会了从不同角度思考问题，分析算法的优劣。

你已掌握的核心能力

  1. 算法思维：能够分析问题本质，选择最优的解题策略。
  2. 编码能力：能够将解题思路转化为清晰、高效、健壮的代码。
  3. 复杂度分析：能够评估算法的时间和空间效率，选择最优解。
  4. 边界处理：能够考虑到各种特殊情况，写出鲁棒性强的代码。

后续挑战（LeetCode Hot 100 链表高频题）

这几道题目只是链表领域的冰山一角，想要成为真正的“链表王者”，还需要攻克以下进阶题目：

  • K 个一组翻转链表 (LeetCode 25)：反转链表的进阶版，难度较大，面试高频硬核题。
  • 相交链表 (LeetCode 160)：寻找两个链表的第一个公共节点，双指针法的巧妙应用。
  • 复制带随机指针的链表 (LeetCode 138)：对链表和哈希表的综合考察，难度较高。
  • 排序链表 (LeetCode 148)：要求 O(n log n) 时间复杂度和常数级空间复杂度，考验算法功底。

四、线性表系列全回顾

从顺序表到单向链表，再到双向带头循环链表，最后到算法实战，我们的线性表系列已经圆满结束：

  1. 入门篇：剖析顺序表缺陷，引出链表的核心设计思想。
  2. 进阶篇：手撸单向不带头非循环链表，攻克指针和二级指针难点。
  3. 高阶篇：实现双向带头循环链表，领略数据结构设计的优雅。
  4. 终篇：实战 LeetCode 经典题目，将理论转化为解题能力。

数据结构与算法的学习之路永无止境，没有捷径可走，唯有多敲代码、多画图、多思考，才能真正掌握其精髓。希望这个系列能成为你坚实的基石，祝你在未来的学习和面试中披荆斩棘，所向披靡！🚀

点赞+收藏+关注，感谢一路以来的支持！我们下一个系列再见！👋

Read more

【贪心算法】day1

【贪心算法】day1

📝前言说明： * 本专栏主要记录本人的贪心算法学习以及LeetCode刷题记录，按专题划分 * 每题主要记录：（1）本人解法 + 本人屎山代码；（2）优质解法 + 优质代码；（3）精益求精，更好的解法和独特的思想（如果有的话）；（4）这个贪心算法正确性的证明 * 文章中的理解仅为个人理解。如有错误，感谢纠错 🎬个人简介：努力学习ing 📋本专栏：C++刷题专栏 📋其他专栏：C语言入门基础，python入门基础，C++学习笔记，Linux 🎀ZEEKLOG主页 愚润泽 你可以点击下方链接，进行其他贪心算法题目的学习 点击链接开始学习贪心day1贪心day2贪心day3贪心day4贪心day5贪心day6贪心day7贪心day8贪心day9贪心day10 也可以点击下面连接，学习其他算法 点击链接开始学习优选专题动态规划递归、搜索与回溯贪心算法 题单获取→ 【贪心算法】题单汇总 题目 * 贪心算法导论 * 860. 柠檬水找零 * 优质解 * 证明 * 2208. 将数组和减半的最少操作次数

By Ne0inhk
【LeetCode面试题17.04】消失的数字

【LeetCode面试题17.04】消失的数字

刷爆LeetCode系列 * LeetCode面试题17.04：消失的数字 * github地址 * 前言 * 题目描述 * 题目与思路分析 * 目标分析 * 思路一：数组哈希 * 思路二：数学求和 * 思路三：位运算（异或） * 代码实现 * 思路一：数组哈希 * 思路二：数学求和 * 思路三：位运算 * 算法代码优化 * 结语 LeetCode面试题17.04：消失的数字 github地址 有梦想的电信狗 前言 本文用C++三种方法实现LeetCode面试题17.04：消失的数字 * 方法一：数组哈希 * 方法二：数学求和再相减 * 方法三：位运算 题目描述 题目链接：https://leetcode.cn/problems/missing-number-lcci/description/ 题目与思路分析

By Ne0inhk
【优选算法必刷100题】第027~28题（前缀和算法）：寻找数组的中心下标、除自身以外数组的乘积

【优选算法必刷100题】第027~28题（前缀和算法）：寻找数组的中心下标、除自身以外数组的乘积

🔥艾莉丝努力练剑：个人主页 ❄专栏传送门：《C语言》、《数据结构与算法》、C/C++干货分享&学习过程记录、Linux操作系统编程详解、笔试/面试常见算法：从基础到进阶 ⭐️为天地立心，为生民立命，为往圣继绝学，为万世开太平 🎬艾莉丝的简介： 🎬艾莉丝的算法专栏简介： 目录 027  寻找数组的中心下标  1.1  算法思路：前缀和 1.2  算法实现 1.2.1  C++实现 1.2.2  Java实现 1.3  博主手记 028  除自身以外数组的乘积 2.1  算法思路 2.2  算法实现

By Ne0inhk
【C语言】排序算法——希尔排序以及插入排序 ——详解！！！

【C语言】排序算法——希尔排序以及插入排序 ——详解！！！

【C语言】排序算法——希尔排序以及插入排序详解 * 前言 * 一 、插入排序 * 1. 视频演示 * 2. 算法思想 * 3. 实现思路 * 4. 代码演示 * 二 、希尔排序 * 1. 视频演示 * 2. 算法思想 * 3. 实现思路 * （1）分组 * （2）预排序 * （3）最终排序 * （4）gap的取值 * 4. 代码演示 * 结语 前言 在学习循环的时候，我们学习到了冒泡排序这个算法 那么，除了冒泡排序，还有什么排序算法呢？ 今天给大家带来的是插入排序以及希尔排序 一 、插入排序 1. 视频演示 首先给大家看一段视频，让大家先看看插入排序是怎么运行的 插入排序演示 2. 算法思想 我们可以从视频里看见，

By Ne0inhk