当前位置：首页 > news >正文

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

news 2026/8/14 13:35:45

单链表是数据结构课程的第一个核心线性结构，也是算法入门与校招面试的必练内容。不同于数组支持下标随机访问，单链表依靠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 为例）

初始：n1=NULL，n2=1，n3=2
第一轮：节点 1 的 next 指向 NULL；n1 移到 1，n2 移到 2，n3 移到 3
第二轮：节点 2 的 next 指向 1；n1 移到 2，n2 移到 3，n3 移到 NULL
第三轮：节点 3 的 next 指向 2；n1 移到 3，n2 移到 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指针，先问自己一句：修改之后，原后继节点还找得到吗？如果找不到，就必须先用临时指针保存下来，防止断链。
边界场景必测清单写完代码后，务必用这几个场景验证：空链表、单个节点、两个节点、目标节点在头部、目标节点在尾部、所有节点都符合删除条件。能覆盖这几个场景，代码基本不会出大问题。
画图辅助调试链表题的指针跳转很抽象，遇到逻辑混乱时，在纸上画出节点和箭头，手动模拟每一步指针的移动，比盯着代码死想高效得多。