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

🏠个人主页：黎雁 🎬作者简介：C/C++/JAVA后端开发学习者 ❄️个人专栏：C语言、数据结构（C语言）、EasyX、游戏、规划、程序人生 ✨ 从来绝巘须孤往，万里同尘即玉京

文章目录

• 【线性表系列终篇】链表试炼：LeetCode Hot 100 经典题目实战解析
• • 文章摘要
  • 一、试炼前的准备：链表解题核心技巧回顾
  • 二、试炼开始：经典题目实战解析
  • • 题目一：反转链表 (LeetCode 206)
    • • 解法一：迭代（双指针）
      • 解法二：递归
    • 题目二：环形链表 (LeetCode 141)
    • • 解法：快慢指针（Floyd判圈算法）
    • 题目三：合并两个有序链表 (LeetCode 21)
    • • 解法一：迭代（虚拟头节点）
      • 解法二：递归
    • 题目四：删除链表的倒数第 N 个结点 (LeetCode 19)
    • • 解法：双指针（间隔法）
  • 三、试炼总结与后续挑战
  • • 你已掌握的核心能力
    • 后续挑战（LeetCode Hot 100 链表高频题）
  • 四、线性表系列全回顾

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

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

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

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

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

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

文章摘要

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

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

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

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

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

二、试炼开始：经典题目实战解析

题目一：反转链表 (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;
* };
*/
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 成为新的头节点
}

复杂度分析：

• 时间复杂度：O(N)，其中 N 是链表的长度。需要遍历链表一次。
• 空间复杂度：O(1)，只使用了几个指针变量，属于原地反转。

边界测试用例：

• 输入 NULL → 输出 NULL
• 输入 [1] → 输出 [1]

解法二：递归

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

代码实现：

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;
}

复杂度分析：

• 时间复杂度：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(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)。有环时，快慢指针相遇时，慢指针走过的距离不会超过链表总长度；无环时，快指针遍历链表一次。
• 空间复杂度：O(1)，只使用了两个指针变量，无需额外空间。

拓展思路：哈希表法 可以使用哈希表存储访问过的节点，遍历链表时如果遇到重复节点则说明有环。但该方法空间复杂度为 O(N)，不如快慢指针法高效。

题目三：合并两个有序链表 (LeetCode 21)

题目描述：将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例： 输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4] 难度：简单 考察频率：⭐⭐⭐⭐⭐

解法一：迭代（虚拟头节点）

解题思路： 这是一个典型的归并操作。直接操作两个链表的头节点会面临边界问题（比如某个链表为空），因此我们引入虚拟头节点 dummy，用 cur 指针构建新链表。

代码实现：

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;
}

复杂度分析：

• 时间复杂度：O(N + M)，其中 N 和 M 分别是两个链表的长度，需要遍历所有节点。
• 空间复杂度：O(1)，只使用了虚拟头节点和几个指针，原地合并。

解法二：递归

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

代码实现：

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;
}
}

复杂度分析：

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

代码实现：

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 停在目标节点的前驱。
• 删除节点后要释放内存，避免内存泄漏。

复杂度分析：

• 时间复杂度：O(N)，只需要遍历链表一次。
• 空间复杂度：O(1)，使用常数级别的额外空间。

三、试炼总结与后续挑战

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

你已掌握的核心能力

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

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

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

四、线性表系列全回顾

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

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

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