单链表经典题型方法链表是数据结构的基础也是笔试面试中的常客。单链表的操作往往考察指针的灵活运用、边界条件的处理以及算法的优化能力。本文精选六道典型例题涵盖查找、删除、反转、重排等常见操作每道题均给出完整的C语言代码、复杂度分析并深入解析难点、易错点及不同解法之间的关联。希望通过这些题目的学习读者能对单链表有一个更深刻的认识。1. 查找单链表倒数第 k 个节点原题解释给定一个带头节点的单链表要求找出倒数第 k 个节点k 为正整数并返回该节点的数据值。如果链表长度小于 k则返回 0或其他约定值。注意头节点不存储数据第一个数据节点是头节点的下一个。算法思路最经典的方法是双指针法快慢指针定义两个指针fast和slow初始都指向头节点。让fast先走 k 步期间若fast变为空说明 k 超出链表长度直接返回 0。然后slow和fast同步向后移动直到fast到达NULL。此时slow指向的节点就是倒数第 k 个节点。为什么fast先走 k 步假设链表有 n 个数据节点不包括头节点头节点视为第 0 个位置。fast从头节点开始走 k 步后指向第 k 个数据节点若 k ≤ n。之后slow从头节点开始两者同步移动当fast走到NULL时fast总共走了 n1 步从头节点到尾节点的下一个而slow同样走了 n1-k 步正好到达第 n1-k 个位置即倒数第 k 个节点因为倒数第 1 个是第 n 个倒数第 k 个是第 n-k1 个n1-k n-k1一致。C语言代码#includestdio.h#includestdlib.htypedefstructNode{intdata;structNode*next;}Node;// 返回倒数第k个节点的数据若不存在返回0intfindKthFromEnd(Node*head,intk){if(headNULL||k0)return0;Node*fasthead;Node*slowhead;// fast先走k步for(inti0;ik;i){if(fastNULL)return0;// 链表长度小于kfastfast-next;}// 同步移动while(fast!NULL){fastfast-next;slowslow-next;}returnslow-data;}复杂度分析时间复杂度O(n)只需一次遍历。空间复杂度O(1)只使用了两个指针。补充分析易错点要注意头节点不存数据fast和slow的初始位置应从头节点开始否则计算会出错。边界条件k 大于链表长度时需返回 0空链表直接返回 0。相似题该题与“求链表的中间节点”都使用了快慢指针但移动策略不同。前者是固定步差后者是速度差。为什么不用数组存储虽然可以遍历一次将所有节点地址存入数组然后通过下标直接访问但需要 O(n) 的额外空间且当链表很长时可能内存不足。双指针法在时间和空间上都更优。2. 查找两个链表的共同后缀第一个公共节点原题解释两个带头节点的单链表例如单词lingering和singing拆分成linger和sing共享后缀ing它们的尾部可能有一部分相同的节点即从某个节点开始后续所有节点地址完全相同。要求找出这个共同后缀的起始节点即第一个公共节点。若没有共同后缀返回空指针。注意比较的是节点地址而非数据值。算法思路采用长度差法分别遍历两个链表跳过各自的头节点计算数据节点的长度 len1 和 len2。让较长的链表先走 |len1 - len2| 步使得两个指针处于距离链表末尾相同长度的位置。然后两个指针同步向后移动每步比较是否指向同一个节点地址相同。第一个相同的节点即为共同后缀的起始位置。若遍历完仍未找到相同节点则说明没有共同后缀。C语言代码typedefstructNode{chardata;// 假设数据为字符实际不影响比较地址structNode*next;}Node;Node*findCommonSuffix(Node*str1,Node*str2){if(str1NULL||str2NULL)returnNULL;// 计算两个链表的长度不包括头节点intlen10,len20;Node*p1str1-next;Node*p2str2-next;while(p1){len1;p1p1-next;}while(p2){len2;p2p2-next;}// 重新指向第一个数据节点p1str1-next;p2str2-next;// 让较长的链表先走长度差步intdifflen1-len2;if(diff0){while(diff--)p1p1-next;}else{diff-diff;while(diff--)p2p2-next;}// 同步移动寻找第一个相同节点while(p1p2){if(p1p2)returnp1;// 找到共同后缀起点p1p1-next;p2p2-next;}returnNULL;// 无共同后缀}复杂度分析时间复杂度O(mn)需要遍历两个链表各一次计算长度和同步查找。空间复杂度O(1)只使用了常数个指针。补充分析难点理解“共同后缀”意味着节点地址相同因此两个链表从该节点开始共享同一段内存。题目中lingering和singing的例子很好地说明了这一点即使单词本身包含相同的字符序列但若地址不同也不算共享后缀。易错点计算长度时要跳过各自的头节点移动较长链表的指针时要注意步数计算正确。与倒数第 k 个节点的相似点两者都利用了“先让一个指针走若干步”的思想来对齐位置。扩展若链表可能带环则需先判断是否有环但本题假设无环。3. 删除链表中绝对值重复的节点原题解释给定一个带头节点的单链表所有节点的数据域满足|data| ≤ n其中 n 为链表长度即数据范围不超过节点个数。要求删除链表中绝对值重复的节点只保留第一次出现的绝对值节点。例如1 → -1 → 2 → 3 → -2 → NULL删除后变为1 → 2 → 3 → NULL因为 -1 绝对值与 1 重复-2 与 2 重复。算法思路利用辅助数组标记法申请一个大小为 n1 的布尔数组flag初始为false用于标记某个绝对值是否已经出现过。遍历链表带头节点使用两个指针prev和curprev指向当前节点的前一个节点cur指向当前节点。初始prev headcur head-next。对于每个cur计算绝对值absVal若flag[absVal]为false说明首次出现将其标记为true然后prev和cur同时后移。若为true说明绝对值已出现过则删除当前节点prev-next cur-next释放cur若需要然后cur更新为prev-next。重复直到cur为空。C语言代码#includestdlib.h#includestdio.h#includemath.h// 包含abs函数typedefstructNode{intdata;structNode*next;}Node;voidremoveDuplicateAbs(Node*head,intn){if(headNULL||head-nextNULL)return;// 申请标记数组初始为0int*flag(int*)calloc(n1,sizeof(int));Node*prevhead;Node*curhead-next;while(cur!NULL){intabsValabs(cur-data);if(flag[absVal]0){flag[absVal]1;// 首次出现标记prevcur;// 保留该节点curcur-next;}else{// 重复出现删除curprev-nextcur-next;free(cur);// 释放内存curprev-next;}}free(flag);}复杂度分析时间复杂度O(n)一次遍历完成删除。空间复杂度O(n)因为需要长度为 n1 的数组记录绝对值出现情况。但由于数据范围与链表长度相同空间开销在合理范围内。补充分析难点理解题目给出的条件|data| ≤ n这是使用数组标记的前提。若没有该条件则需先遍历找出最大绝对值以确定数组大小或改用哈希表。易错点数组下标不能越界确保absVal在 0~n 之间。删除节点时要正确链接prev-next并释放被删节点内存若题目要求。注意prev指针的更新只有在保留节点时prev才移动到cur删除节点时prev不动因为cur已经更新。与其他题的异同该题使用了辅助数组而前两题都只用了 O(1) 空间。这种空间换时间的策略在特定条件下有效。变体若不给出 n可以先遍历一次链表找出最大绝对值再申请数组这样会多一次遍历但总复杂度仍为 O(n)。4. 反转链表带头节点反转链表是最基础也是最重要的链表操作之一。这里介绍两种方法经典三指针法和利用头节点的两指针头插法同学提供思路。4.1 经典三指针法prev、curr、next原题解释给定一个带头节点的单链表要求将数据节点部分反转并返回原头节点头节点不变其next指向反转后的第一个数据节点。算法思路使用三个指针prev指向已反转部分的前一个节点初始为 NULLcurr指向当前待处理节点next用于保存curr的下一个节点。每次迭代保存next curr-next将curr-next指向prev反转prev和curr分别前移一步prev curr,curr next循环结束后prev指向原链表的最后一个节点即新链表的第一个数据节点。最后将头节点的next指向prev。C语言代码Node*reverseList(Node*head){if(headNULL)returnNULL;// 空链表处理Node*prevNULL;Node*currhead-next;// 第一个数据节点Node*next;while(curr!NULL){nextcurr-next;// 保存下一个节点curr-nextprev;// 反转指向prevcurr;// prev 前移currnext;// curr 前移}head-nextprev;// 头节点指向反转后的第一个节点returnhead;}复杂度分析时间复杂度O(n)遍历一次。空间复杂度O(1)。4.2 利用头节点的两指针头插法同学提供原题解释这种方法利用头节点作为“锚点”每次将当前节点移动到头部类似头插法从而实现原地反转。只需两个指针i和j。算法思路以head → 1 → 2 → 3 → 4 → NULL为例初始化i head-next指向第一个数据节点 1j i-next指向第二个数据节点 2并将i-next置为 NULL使 1 成为新链表的尾节点。循环直到j为空将头节点的next指向j即把当前节点拉到头部j后移一位j j-next将刚拉到头部的节点的next指向之前的i即已反转部分更新i为当前头部节点i head-next循环结束后链表已反转。C语言代码voidreverseList_alternative(Node*head){if(headNULL||head-nextNULL)return;// 空或只有一个节点Node*ihead-next;// 第一个数据节点Node*ji-next;// 第二个数据节点i-nextNULL;// 第一个节点变为尾节点while(j!NULL){head-nextj;// ① 头节点指向当前节点 jjj-next;// ② j 后移head-next-nexti;// ③ 新头节点指向之前的 iihead-next;// ④ 更新 i 为新头}// 循环结束后i 指向反转后的第一个数据节点头节点已正确指向它}代码解读同学提供的详细讲解该方法巧妙地利用头节点作为固定点每次将当前节点插入到头部逐步构建反转链表。其指针变化顺序至关重要先让头节点指向当前节点再移动j保存下一个节点然后将当前节点的next指向之前已反转的部分最后更新i。整个过程只需两个指针但逻辑稍显隐蔽。两种方法的对比经典三指针法逻辑清晰容易理解是反转链表的标准写法。头插法变种代码简洁但指针更新顺序容易出错需要仔细推演。两者时间复杂度相同空间均为 O(1)。推荐优先掌握经典方法。补充分析易错点忘记保存next指针会导致断链。循环终止条件要正确curr ! NULL或j ! NULL。头插法中第一步将第一个节点next置 NULL 是必要的否则会形成环。相似题反转链表常作为子步骤出现在更复杂的题目中如后面的重排序链表。5. 删除链表的中间节点原题解释给定一个单链表带头节点要求删除它的中间节点。如果链表长度为偶数规定删除靠前的那个中间节点。例如长度为 1删除唯一节点链表变空。长度为 2删除第一个节点。长度为 3删除第二个节点。长度为 4删除第二个节点靠前。算法思路采用快慢指针同时使用哑节点简化头节点可能被删除的情况创建哑节点dummy其next指向头节点这里头节点指第一个数据节点但为了统一我们传入带头节点的头指针并让哑节点指向它。定义慢指针slow初始指向哑节点快指针fast初始指向头节点即第一个数据节点。每次快指针走两步慢指针走一步当快指针无法再走两步时慢指针恰好指向待删节点的前一个节点。然后执行删除操作slow-next slow-next-next并释放被删节点。C语言代码带头节点版本Node*deleteMiddle(Node*head){if(headNULL||head-nextNULL)returnhead;Node dummy;dummy.nexthead;Node*slowdummy;Node*fasthead-next;while(fast-next!NULLfast-next-next!NULL){fastfast-next-next;slowslow-next;}Node*delslow-next;slow-nextdel-next;free(del);returndummy.next;}边界情况验证数据节点个数示例带头节点删除后说明0head→NULLhead→NULL直接返回1head→1→NULLhead→NULL删除唯一节点2head→1→2→NULLhead→2→NULL删除第一个节点3head→1→2→3→NULLhead→1→3→NULL删除第二个节点4head→1→2→3→4→NULLhead→1→3→4→NULL删除靠前的第二个节点复杂度分析时间复杂度O(n)一次遍历。空间复杂度O(1)。补充分析难点快慢指针的移动条件要确保慢指针最终指向待删节点的前驱。如果链表长度为偶数且删除靠前中间节点则快指针最后一步可能无法走完两步此时慢指针正好停在正确位置。易错点快指针移动前需检查fast-next是否为空避免访问空指针。使用哑节点可以避免对头节点被删除的特殊处理。与其他题的相似点同样使用了快慢指针与查找倒数第 k 个节点异曲同工但前者是速度差后者是固定步差。6. 重排序链表L’ (a1, an, a2, a_{n-1}, …)原题解释给定一个带头节点的单链表 L (a1, a2, …, an)要求将其重新排列为 L’ (a1, an, a2, a_{n-1}, a3, a_{n-2}, …)。例如输入1 → 2 → 3 → 4 → 5 → NULL输出1 → 5 → 2 → 4 → 3 → NULL输入1 → 2 → 3 → 4 → 5 → 6 → NULL输出1 → 6 → 2 → 5 → 3 → 4 → NULL算法思路采用三步走策略空间复杂度 O(1)找中点并断开使用快慢指针找到后半部分的起始节点slow同时用prev记录前半部分的最后一个节点然后将prev-next置为 NULL得到前后两个独立链表。反转后半部分调用反转函数将后半部分链表反转。合并将前半部分和反转后的后半部分交替合并前半部分取一个后半部分取一个循环直至短链表结束最后将剩余部分接上。C语言代码voidreorderList(Node*head){if(headNULL||head-nextNULL)return;// 快慢指针找中点Node*slowhead-next;Node*fasthead-next;Node*prevhead;while(fast-next!NULLfast-next-next!NULL){fastfast-next-next;prevslow;slowslow-next;}// 断开prev-nextNULL;// 反转后半段Node*secondreverseDataNodes(slow);Node*firsthead-next;// 交叉合并Node*t1,*t2;while(first!NULLsecond!NULL){t1first-next;t2second-next;first-nextsecond;second-nextt1;firstt1;secondt2;}}复杂度分析时间复杂度O(n)每个节点被访问常数次找中点、反转、合并各一次遍历。空间复杂度O(1)只使用了几个指针和一个栈上哑节点。补充分析难点找中点时需要区分奇数长度和偶数长度的情况。上述代码中fast每次走两步循环结束后若链表长度为奇数slow指向正中间若为偶数slow指向后半部分的第一个节点即靠后的中间节点。而题目要求重排时前半部分和后半部分的长度关系正好满足合并需求。断开链表时要确保prev正确否则会丢失后半部分。易错点反转后半部分时若后半部分为空如链表只有一个节点需单独处理但函数开头已排除。合并时要注意指针更新顺序防止断链。最后头节点要指向合并后的链表。与其他题的关联该题综合了找中点、反转链表、合并三个基础操作是前几道题的综合应用。熟练掌握前几个技巧此题便迎刃而解。总结通过以上六道例题我们系统学习了单链表的常见解题技巧题目核心技巧时间复杂度空间复杂度关键点查找倒数第k个节点双指针固定步差O(n)O(1)快指针先走k步找共同后缀长度差法O(mn)O(1)先对齐再同步比较地址删除绝对值重复节点辅助数组标记O(n)O(n)利用数据范围限制空间换时间反转链表经典三指针O(n)O(1)保存后继逐个反转反转链表头插法两指针头节点O(n)O(1)每次将当前节点插入头部删除中间节点快慢指针速度差O(n)O(1)慢指针指向待删节点的前驱重排序链表找中点 反转 合并O(n)O(1)三步走综合前几个技巧易错点总结指针操作前必须先判断是否为空。修改节点next前一定要保存后续节点地址避免断链。带头节点的链表要注意头节点不存数据遍历和计数时需区分。双指针法中的循环条件要仔细推演确保边界正确。释放内存时要确保不再使用该指针。学习建议先理解每个题目的原理再动手画图模拟指针变化。自己实现一遍代码并测试各种边界情况。对比相似题目的异同总结规律。尝试一题多解拓宽思路。希望这篇博客能帮助你了解和掌握单链表的核心算法。同时由于笔者水平有限本文可能有疏漏敬请读者朋友交流指正。