【线性表系列终篇】链表试炼：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

进来了解一下python的深浅拷贝

进来了解一下python的深浅拷贝

深浅拷贝是什么：在Python中，理解深拷贝（deep copy）和浅拷贝（shallow copy）对于处理复杂的数据结构，如列表、字典或自定义对象，是非常重要的。这两种拷贝方式决定了数据在内存中的复制方式，进而影响程序的运行结果 浅拷贝： 1. 浅拷贝的定义： 浅拷贝是一种复制操作，它创建一个新对象，并将原对象的内容复制到新对象中。对于原对象内部的子对象，浅拷贝不会递归地复制它们，而是直接引用这些子对象。因此，浅拷贝后的对象和原对象共享内部的子对象。 2. 浅拷贝的实现方式 （1）使用 copy 模块的 copy() 函数 import copy original_list = [1, 2, [3, 4]] shallow_copied_list = copy.copy(original_list)  （2）使用列表、

By Ne0inhk

Python 真实世界的数据科学（十二）

原文：Python: Real-World Data Science 协议：CC BY-NC-SA 4.0 四十二、使用回归分析预测连续目标变量 在前几章中，您了解了监督学习背后的主要概念，并为分类任务训练了许多不同的模型以预测组成员或分类变量。 在本章中，我们将深入研究监督学习的另一个子类别：回归分析。 回归模型用于在连续规模上预测目标变量，这使它们对于解决科学和工业应用中的许多问题具有吸引力，例如理解变量之间的关系，评估趋势或进行预测。 一个例子是预测未来几个月公司的销售额。 在本章中，我们将讨论回归模型的主要概念，并涉及以下主题： * 探索和可视化数据集 * 研究实现线性回归模型的不同方法 * 训练对异常值具有鲁棒性的回归模型 * 评估回归模型并诊断常见问题 * 将回归模型拟合到非线性数据 介绍一个简单的线性回归模型 简单（单变量）线性回归的目标是为单个特征（解释变量x）与连续值响应之间的关系建模的模型（ 目标变量和）。 具有一个解释变量的线性模型方程定义如下： https://github.com/OpenDocCN/freelearn-ds-z

By Ne0inhk
Ubuntu系统下Python连接国产KingbaseES数据库实现增删改查

Ubuntu系统下Python连接国产KingbaseES数据库实现增删改查

摘要：本文将介绍Ubuntu系统下如何使用Python连接国产金仓数据库KingbaseES，并实现基本的增删改查操作。文中将通过具体代码示例展示连接数据库、执行SQL语句以及处理结果的全过程。这里把Python连接KingbaseES的经验整理一下，希望能帮到同样踩坑的兄弟。 目录 1.环境准备与驱动安装 1.1 科普ksycopg2知识 1.2 官方下载ksycopg2驱动 1.3 安装ksycopg2驱动 2. 连接KingbaseES数据库 3. 创建数据表 4. 实现增删改查功能 4.1 新增 4.2 查询 4.3 修改 4.4 删除 4.5 封装一个类crud方便复用 5.总结 1.环境准备与驱动安装 KingbaseES提供了专门的Python驱动包ksycopg2，它是基于Python DB API 2.0规范实现的线程安全数据库适配器！

By Ne0inhk