单链表专题（一）-应用篇：三道经典题吃透删除、反转与快慢指针

单链表是数据结构课程的第一个核心线性结构也是算法入门与校招面试的必练内容。不同于数组支持下标随机访问单链表依靠next指针串联节点所有操作都围绕「指针指向修改」展开极其考验对边界场景的把控能力。本文以三道最经典的单链表应用题为例从思路推导到代码实现、从易错点复盘到算法思想升华系统梳理单链表的核心操作与解题套路。一、单链表基础回顾单链表的每个节点由「数据域」和「后继指针域」组成只能从头节点出发单向遍历无法反向访问也不能直接通过下标定位节点。 C 语言中节点的标准定义如下struct ListNode { int val; struct ListNode *next; }; typedef struct ListNode ListNode;单链表操作的三大核心特点已知前驱节点时插入 / 删除节点的时间复杂度为 O (1)只需修改指针指向无需移动元素。访问任意节点必须从头遍历时间复杂度 O (n)不支持随机访问。头节点可能发生变化如删除头节点、反转链表是最容易出错的边界点。在开始刷题前先记住单链表的通用避坑原则访问ptr-val或ptr-next前必须确保ptr不为NULL否则会触发空指针崩溃。修改节点的next指针前先保存原后继节点避免链表断裂、遍历中断。重新拼接链表后必须确保最终尾节点的next NULL标记链表结束。二、经典题逐题精讲2.1 移除链表元素LeetCode 203题目描述给你一个链表的头节点head和一个整数val请你删除链表中所有满足Node.val val的节点并返回新的头节点。题意分析这道题是单链表「删除操作」的入门题核心难点不在删除逻辑本身而在边界场景头节点本身就是要删除的节点新头节点会变化链表尾部是要删除的节点链表所有节点都需要删除最终返回空链表链表本身就是空链表解法一尾插法构建新链表这是最符合直觉的思路不直接在原链表上做剪断删除而是遍历原链表把值不等于val的合法节点按原有顺序重新拼接成一个新链表。完整代码struct ListNode* removeElements(struct ListNode* head, int val) { // 新链表的头、尾指针初始为空 ListNode *newHead, *newTail; newHead newTail NULL; ListNode *pcur head; // 遍历原链表 while(pcur) { if(pcur-val ! val) { // 当前节点需要保留尾插到新链表 if(newHead NULL) { // 新链表为空第一个节点同时是头和尾 newHead newTail pcur; } else { // 接到尾部尾指针后移 newTail-next pcur; newTail newTail-next; } } pcur pcur-next; } // 关键收尾新链表非空时尾节点next置空 if(newTail ! NULL) { newTail-next NULL; } return newHead; }思路细节拆解天然解决头节点删除问题第一个被保留的节点自然成为新头无需单独判断原头节点是否要删。尾节点置空是必写步骤如果原链表尾部是要删除的节点新链表最后一个节点的next仍会指向原链表的无效节点必须手动置空标记链表结束。空指针防护如果所有节点都被删除newTail仍为NULL必须先判断非空再访问next。解法二虚拟头节点原地删除这是链表删除题的工业级标准写法核心是在原链表头部加一个「哨兵节点dummy」让所有待删除节点都成为 “某个节点的后继”删除逻辑完全统一。完整代码struct ListNode* removeElements(struct ListNode* head, int val) { // 创建虚拟头节点next指向原链表头 ListNode dummy; dummy.next head; ListNode* cur dummy; while (cur-next ! NULL) { if (cur-next-val val) { // 下一个节点要删除直接跳过该节点 cur-next cur-next-next; } else { // 下一个节点保留指针后移 cur cur-next; } } return dummy.next; }这种写法的优势非常明显无需单独处理头节点无需手动置空尾节点代码更简洁边界场景全部自动兼容。2.2 反转链表LeetCode 206题目描述给你单链表的头节点head请你反转链表并返回反转后的链表。题意分析反转链表的本质是把每个节点的next指针从「指向后继」改为「指向前驱」。最大的难点是直接修改当前节点的next会丢失后继节点导致链表断裂、遍历无法继续。解法三指针迭代原地反转这是面试的标准最优解空间复杂度 O (1)全程只通过三个指针配合逐个翻转节点指向。完整代码struct ListNode* reverseList(struct ListNode* head) { if(head NULL) { return head; } ListNode *n1, *n2, *n3; n1 NULL; // 前驱节点 n2 head; // 当前节点 n3 head-next; // 后继节点提前保存防止断链 while(n2) { // 翻转当前节点的指向 n2-next n1; // 三个指针整体后移 n1 n2; n2 n3; if(n3) { n3 n3-next; } } return n1; }三个指针的分工n1记录当前节点的前驱节点也就是反转后当前节点要指向的目标。初始为NULL因为原头节点反转后会变成尾节点。n2当前正在处理的节点从原头节点开始逐个向后遍历。n3提前保存当前节点的后继节点相当于 “备份后路”。修改n2-next后原后继会丢失必须提前存下来。执行流程模拟以 1→2→3→NULL 为例初始n1NULLn21n32第一轮节点 1 的 next 指向 NULLn1 移到 1n2 移到 2n3 移到 3第二轮节点 2 的 next 指向 1n1 移到 2n2 移到 3n3 移到 NULL第三轮节点 3 的 next 指向 2n1 移到 3n2 移到 NULL循环结束此时 n1 指向原链表最后一个节点也就是反转后的新头节点直接返回即可。拓展递归解法递归写法代码更简洁核心思想是 “先递归到链表尾部再从后往前逐个翻转”。struct ListNode* reverseList(struct ListNode* head) { // 终止条件空链表或只有一个节点无需反转 if (head NULL || head-next NULL) { return head; } // 先反转子链表得到子链表的新头 ListNode* newHead reverseList(head-next); // 把当前节点接到子链表尾部 head-next-next head; // 当前节点变为尾节点置空防止成环 head-next NULL; return newHead; }2.3 链表的中间结点LeetCode 876题目描述给你单链表的头结点head请你找出并返回链表的中间结点。如果有两个中间结点则返回第二个中间结点。题意分析单链表不能随机访问朴素做法是「先遍历一遍统计长度再从头走长度的一半」但需要两次遍历。 这道题的最优解是快慢指针龟兔赛跑算法只需一次遍历就能找到中点也是单链表最经典的算法思想之一。核心算法快慢指针利用两个指针的速度差实现定位慢指针slow一次走 1 步快指针fast一次走 2 步因为快指针速度是慢指针的 2 倍当快指针走到链表末尾时慢指针走过的路程刚好是一半正好停在中间位置。完整代码struct ListNode* middleNode(struct ListNode* head) { ListNode *Fast, *Slow; Fast Slow head; while(Fast Fast-next) { Slow Slow-next; Fast Fast-next-next; } return Slow; }循环条件深度解析while(Fast Fast-next)是这道题最核心的细节有两个关键点顺序不能反利用 C 语言的短路求值特性先判断Fast是否为空如果Fast已经是 NULL程序不会再访问Fast-next完美避免空指针崩溃。决定了中点落点这个条件会让快指针最终停在「最后一个节点的下一位NULL」因此偶数长度时慢指针正好落在第二个中间节点上完全符合题目要求。场景验证奇数长度5 个节点快指针停在最后一个节点慢指针停在第 3 个节点正中间偶数长度6 个节点快指针停在 NULL慢指针停在第 4 个节点第二个中间节点拓展与延伸如果题目要求返回第一个中间节点只需修改循环条件while(Fast-next Fast-next-next)快慢指针的应用远不止找中点它还是解决「判断链表是否有环」「找环的入口节点」「找链表倒数第 k 个节点」等经典题的核心思想是单链表必须掌握的算法套路。三、单链表解题通用方法论做完这三道题我们可以提炼出单链表应用题的通用解题框架头节点变化的两种处理方案只要题目可能修改头节点删除、反转、排序要么用「新链表 新头指针」要么用「虚拟头节点」两种思路都能避免单独处理头节点的冗余逻辑。指针修改的铁则凡是要修改节点的next指针先问自己一句修改之后原后继节点还找得到吗如果找不到就必须先用临时指针保存下来防止断链。边界场景必测清单写完代码后务必用这几个场景验证空链表、单个节点、两个节点、目标节点在头部、目标节点在尾部、所有节点都符合删除条件。能覆盖这几个场景代码基本不会出大问题。画图辅助调试链表题的指针跳转很抽象遇到逻辑混乱时在纸上画出节点和箭头手动模拟每一步指针的移动比盯着代码死想高效得多。写在最后这三道题是单链表的「基石题」覆盖了删除、反转、快慢指针三大核心考点。把这三道题的每一行代码、每一个边界条件都吃透再去学习合并有序链表、环形链表、相交链表等进阶题目时就会发现核心逻辑都是相通的。数据结构的学习没有捷径多写、多画、多踩坑、多复盘慢慢就能建立起对指针操作的直觉。