刷到第5期终于轮到链表了。说实话链表在LeetCode里的地位有点特殊你说它难吧核心思路翻来覆去就那么几种你说它简单吧我在刷题群里见过太多人“看题全会一写就废”反转链表写了三遍还是绕不清指针。这次我把从基础遍历到排序、相交、环检测、K个一组翻转遇到的典型问题都整理成文包括我实际踩过的坑、压箱底的调试技巧和普通人可复用的刷题路线希望能帮你少走弯路。这篇内容适合三类人正在刷LeetCode准备面试的求职者、被数据结构课程设计折磨的学生党热搜里的“单链表的基本操作实验”、“c语言链表”说的就是这类需求以及想把链表基础打扎实的初学者。我会按“思路—题目—实战—语言—规划”的顺序展开考虑到热搜里混着“基本计算器”、“994腐烂的橘子”、“爱吃香蕉的狒狒”这类跟链表完全无关的热词我也会顺便聊两句怎么防止被热门题带偏节奏。1. 链表题的整体思路先别急着写码把结构画明白1.1 链表题为什么“会看不会写”我见过不少同学链表题的题解看得很顺代码也背得下来可一到自己写就卡住。根子在于数组的操作是“改一个下标”而链表的操作是“改一堆指针”。指针一多脑子里那幅图没画清楚代码自然就乱了。链表就像一列火车每节车厢是一个节点里面装着数据val和一根挂钩next。你要做插入、删除、反转本质上就是在改挂钩的指向。只不过这个改法有个致命特点——顺序错了链子就断了。比如删除节点B你得先让A.next绕过B指向C再考虑释放B反过来先操作B.next节点C就找不到了。这种“先接后断”的顺序感是需要专门训练的。另外LeetCode上的链表题几乎全是单向链表而且普遍不给你头节点的前驱。这意味着你想操作头节点时时常要额外造一个“哑节点”来统一逻辑这个技巧我在后面专门讲。1.2 我把刷链表题的固定套路总结成了四步刷了大概40道链表题之后我总结出一个固定流程每次拿到新题都按这四步走先画图、再写代码基本不会卡壳。第一步用方框和箭头把给定的链表画出来然后把题目要求的最终状态在旁边也画一遍。第二步找“操作边界”哪些节点的next会变哪个节点可能成为新头节点有没有可能操作到空指针。第三步决定要不要哑节点凡是“可能需要处理头节点”的删除类、反转类题目我习惯开头就加一个dummy省掉一堆if判断。第四步写代码时嘴里默念“先取、再指、后断”也就是先把要用的节点用变量存住再修改指针。这套流程听起来简单真能坚持的人不多。链表题最忌讳一上来就写脑内模拟一遍再动手代码正确率能提升一大截。2. 必练的十大经典链表题从遍历到排序一网打尽2.1 热门前100题里的链表题分布LeetCode热门100题里链表题大概占十二三道。结合我自己的刷题记录和热搜词把出现频率最高的几类整理成了一张表方便你按专题集中训练题目类型典型题目核心考点链表遍历876. 链表的中间结点快慢指针找中点单链表逆序206. 反转链表三指针迭代/递归链表相交160. 相交链表双指针走完对方路线链表排序148. 排序链表、147. 对链表进行插入排序归并排序、断链重接链表删除19. 删除链表的倒数第N个结点一次遍历哑节点链表合并21. 合并两个有序链表、23. 合并K个升序链表穿针引线、分治环检测141. 环形链表、142. 环形链表 II快慢指针数学推导K个一组翻转25. K 个一组翻转链表分段反转连接这些题刷完链表题就不再是靠记忆而是靠肌肉记忆了。下面几节我挑几个典型的展开讲讲实操时容易出问题的地方。2.2 单链表逆序LeetCode 206三指针迭代法反转链表是当之无愧的链表第一题面试手撕概率极高。很多教程会先讲递归但我更建议新手从迭代的三指针法入手因为递归虽然代码短理解门槛反而高。核心逻辑是准备三个指针pre初始为Nonecur指向headnxt用来保存cur.next。每轮循环做四件事存住cur.next把cur.next指向prepre挪到curcur挪回nxt。循环结束时pre就是新头节点。为什么先存nxt因为cur.next一旦被改写原来后面的节点就找不到了必须先“备份”。我用Python写一版可以直接跑的class ListNode: def __init__(self, val0, nextNone): self.val val self.next next def reverseList(head: ListNode) - ListNode: pre None cur head while cur: nxt cur.next # 1. 先备份下一个节点 cur.next pre # 2. 反转指针 pre cur # 3. pre 前移 cur nxt # 4. cur 前移 return pre这段代码最大的坑有三个一是忘记第1步的备份二是循环条件写成while pre.next三是最后return了cur而不是pre。只要你画图时候脑子里有一列火车在掉头这三步就不会错。2.3 链表相交LeetCode 160双指针的巧妙之处找两个链表相交节点的经典做法是双指针法。两个指针分别从headA和headB出发走完自己的链表后再走到对方的链表上去。假设链表A长度为a链表B长度为b相交部分长度为c那么两个指针在“彼此都走完ab-c步”的时候恰好会同时停在相交节点上。这个思路说穿了就是“让两个人走过的总路程相等”。我第一次看到题解时觉得很巧妙但自己写的时候总担心死循环——其实只要两个链表都无环指针走完null再跳到对方链表最多走ab步要么相遇要么同时到null不会死循环。参考代码def getIntersectionNode(self, headA: ListNode, headB: ListNode) - ListNode: p1, p2 headA, headB while p1 ! p2: p1 p1.next if p1 else headB p2 p2.next if p2 else headA return p1注意这里判断的是“p1是否为None”而不是“p1.next是否为None”这样当两个链表没有交点时两个指针会同时走到None循环退出返回None语义正好正确。如果你写成p1.next两个链表不相交的情况就会在None处卡死。2.4 链表排序LeetCode 148/147归并排序专治链表链表的随机访问是O(1)取下标排序必须靠“走指针”完成所以快排这种依赖下标的算法在链表上写起来很别扭。链表排序的标准答案是归并排序第一步用快慢指针找到中点第二步递归排序左右两半第三步合并两个有序链表。找中点有个经典细节快指针走两步慢指针走一步循环条件是fast and fast.next。很多人写成fast.next and fast.next.next结果单节点链表直接报错。我自己的写法是def sortList(head: ListNode) - ListNode: if not head or not head.next: return head # 找中点将链表切分为两半 fast, slow head.next, head while fast and fast.next: slow slow.next fast fast.next.next mid slow.next slow.next None # 切断 left sortList(head) right sortList(mid) return mergeTwoLists(left, right)切断链表这步太重要了漏掉它递归就会死循环。合并函数我习惯用哑节点接尾往下看2.6节。如果面试官追问“能不能不用O(nlogn)”可以提一句对链表插入排序147题是O(n²)适合基本有序的链表但一般不会让你手写因为边界条件实在多。2.5 链表遍历与删除击穿“倒数第N个”LeetCode 19“删除链表的倒数第N个结点”是另一道高频题。常规思路是先遍历一遍数总长度再走第二次找到待删节点的前驱——这当然能过但面试官更想看到“一次遍历”的解法快指针先走N步然后快慢指针同步走等快指针走到尾慢指针刚好停在待删节点的前驱。这里有两个必须注意的点第一快指针走N步时要判断链表长度是否足够不够就直接返回第二删除头节点时慢指针没有前驱所以强烈建议加哑节点def removeNthFromEnd(head: ListNode, n: int) - ListNode: dummy ListNode(0, head) fast dummy slow dummy for _ in range(n): fast fast.next while fast.next: fast fast.next slow slow.next slow.next slow.next.next return dummy.next为什么最后返回dummy.next而不是head因为被删的节点可能就是头节点dummy.next才能正确指向新头。这个细节我面试时就吃过亏删了头节点还返回原来的head白给。2.6 链表合并与环检测高频变形题扩展合并两个有序链表21题我强烈建议用“哑节点尾插法”。定义dummy和tail谁小谁接上最后接剩余部分返回dummy.next。这个写法在合并K个升序链表23题里配合优先队列就是一套完整的思路。环检测141题其实就是反转链表、找中点里快慢指针的亲戚慢指针走一步快指针走两步如果快指针追上了慢指针就说明有环。追不追得上数学上取决于快指针每次比慢指针多走一步所以只要有环二者的距离就一定会逐步缩短到0。142题求环入口时公式推导是“头节点到环入口的距离 相遇点继续走到环入口的距离”记不住公式没关系画一个简单环形图现场推一遍最快。3. 实操记录我踩过的五个链表的坑3.1 空指针与next链断裂链表题报错频率最高的就是AttributeError: NoneType object has no attribute next。原因无外乎两种一是你在不确定当前节点是否为空时直接访问了next二是循环末尾cur已经变成了None下一轮开头又访问cur.next。我的自查办法每次写完链表代码先通读一遍把所有出现.next的地方用荧光笔标出来然后逐个问自己“这里的节点有没有可能为None”。如果有可能就加一行if判断。这个习惯帮我至少减少了一半的提交报错。3.2 快慢指针的循环判断快慢指针在找中点、环检测、找倒数第N个节点里反复出现但循环条件特别容易写错。我踩过的坑是找中点时把while fast and fast.next写成了while fast.next and fast.next.next结果fast为None时直接崩了。统一的标准是只要快指针会一次性走两步循环条件就必须同时检查fast和fast.next不为空。至于为什么是这样而不是“fast.next and fast.next.next”简单记因为fast本身可能是None先判断它最保险。3.3 哑节点的正确打开方式哑节点的英文叫dummy node核心价值是“消除对头节点的特殊化处理”。最典型的场景是删除头节点没有哑节点你得写if head.val target: head head.next之类的分支有了哑节点所有节点的删除逻辑完全统一。用法上有个小细节dummy ListNode(0, head)之后你要操作的是dummy这个链表而不是head。最后return dummy.next不要心一软return head。我见过有人建了哑节点最后却返回原head等于白费力气。3.4 递归反转别在长链表上硬扛206题很多人也提供递归写法def reverseList(self, head: ListNode) - ListNode: if not head or not head.next: return head new_head self.reverseList(head.next) head.next.next head head.next None return new_head这段代码逻辑是对的但对一个非常长的链表递归时Python默认递归深度约1000链表长度一长就会RecursionError。面试时写了递归最好自己主动补一句“这个写法在链表很长时可能栈溢出所以我更推荐迭代法”既展示思路全面又避免被追问时尴尬。3.5 边界条件空链表、单节点与双节点我刷链表题最大的心得是空链表、单节点、双节点这三种输入必须开头就处理。很多题看起来代码写完了一提交挂在特殊用例上就是因为边界漏了。我的做法是每次写完代码先手动测试三个用例head为None、只有一个节点、只有两个节点。尤其是反转链表只有两个节点时最容易写错还有删除类题目删头节点和删尾节点也是高危区。4. 语言选型与数据结构基本功C语言、Python 怎么选4.1 C语言链表的基本语法结构体与指针如果是“单链表的基本操作实验”这类作业老师十有八九要求用C语言写因为要你练malloc和指针。C语言里链表节点的标准定义是struct Node { int val; struct Node *next; };创建节点的核心是malloc分配内存千万别漏了stdlib.h头文件struct Node* createNode(int val) { struct Node* node (struct Node*)malloc(sizeof(struct Node)); node-val val; node-next NULL; return node; }C语言链表操作里最容易丢分的是“释放内存”。链表的清空不是置空指针就完事而是遍历每个节点free最后把头指针也设为NULL。很多同学写clearList只写head NULL内存泄漏一大堆实验报告里也看不出问题但严格来说是不合格的。4.2 Python链表不是“有手就行”细节回事Python做LeetCode链表题很舒服不需要管内存但有一件事必须想明白Python对象是引用语义head、cur、pre这些变量本质上都是对象的引用改来改去还是在操作同一块对象。这带来一个容易踩坑的问题你把head赋值给cur后对cur.next的修改会直接反应到原链表上但如果你给cur重新赋值cur cur.next那只是让cur这个“标签”换了个指向原来的对象不会变。理解这点调试指针问题时才不至于一头雾水。4.3 循环单链表与双链表的几个高频考点循环单链表是尾节点的next指向头节点这带来两个好处一是从任意节点出发都能遍历到所有节点二是约瑟夫环这类问题天然适合用它模拟。判断一个循环链表的结束条件是cur.next head而不是cur.next None。双链表则是每个节点多了一个prev指针插入删除时要注意的操作顺序比单链表多一倍插入一个新节点理论上要改四个指针。虽然LeetCode核心题里双链表出现频率不算高但像LRU缓存这类热门设计题底层数据结构的首选就是“哈希表双向链表”所以还是建议花两小时把双链表的基本操作写熟。4.4 链表的基本操作创建、插入、删除、清空数据结构实验里链表的五大基本操作最好能形成肌肉记忆创建头插法或尾插法。头插法结果是逆序的尾插法需要一个tail指针记录尾部。指定位置插入热搜里有“在指定位置插入建立单链表”这个需求核心是先找到第i-1个节点newNode-next p-nextp-next newNode顺序绝对不能反。删除找到目标节点的前驱prepre-next target-next然后free(target)。遍历从head开始while cur ! NULL访问cur-valcur cur-next。清空遍历free每个节点最后head NULL。这五个操作练熟再配合LeetCode那些进阶题链表的底子就算真打牢了。刷题时不光要看懂题解我建议把每个题都用C和Python各写一遍C帮你理解内存Python帮你练思路互相印证效果很好。5. 刷题顺序与时间投入普通人也能一个月拿下链表5.1 我的链表刷题顺序递增难度按照我个人经验链表题最好按下面这个顺序刷难度是平滑上升的不会一上来就把信心打没基础操作遍历、寻找中间节点876翻转与合并反转链表206、合并两个有序链表21删除类删除倒数第N个结点19、删除排序链表中的重复元素83双指针进阶相交链表160、环形链表141、142排序与分组排序链表148、对链表进行插入排序147综合难题K个一组翻转链表25、合并K个升序链表23这个顺序的特点是每一步都用得上前面学过的技巧。比如做25题时你需要同时用到反转链表和找区间的边界处理做23题时21题的合并逻辑是直接拿来用的。5.2 每天刷几题、复盘节奏怎么安排对非全职刷题的人来说我建议每天两题一题新题、一题复习昨天的旧题。链表题的通病是一周不碰手就生所以复习比刷新题更重要。具体节奏第一天做206反转链表第二天先把206盲写一遍不看答案再做21题第三天复习21题再做19题。这样滚动往前走十天就能把核心链表题过一轮。不要贪多每天五六题看起来爽三天后全忘光等于白刷。5.3 周赛430、热门100题怎么用LeetCode周赛比如热搜里的“leetcode周赛430”适合作为阶段检测而不是入门学习手段。周赛的T1通常偏简单T2/T3刚好能覆盖常见链表技巧做完后把题解里的链表操作复盘一遍比闷头刷十道题还管用。热门100题的意义在于拿下高频考点但这里要提醒一句搜索“链表”时搜出来的热词里经常混着“994腐烂的橘子”BFS、“基本计算器”栈、“爱吃香蕉的狒狒”二分查找这类非链表的题目。它们确实是热门题但不是你练链表时该看的。我当时就吃过这个亏列举题单时把它们混进了链表练习计划结果花了半天调一个跟链表完全不沾边的搜索题。刷题前先确认题目考察的核心数据结构比盲目跟着热词走更重要。我个人在实际操作中的体会是链表题说白了就是考你指针引用操作的熟练度它不像动态规划那样需要抽象建模能力更像是一套需要反复练到形成肌肉记忆的基本功。你只要保证每一道题都亲手画过图、亲手写过、亲手调试过一个月下来再去面试考场看到链表题心里是有底的。最后分享一个我一直在用的技巧无论C还是Python我都会先写一个printList函数把链表从头到尾打印一遍调试时先看打印结果、再猜逻辑问题。写链表题最怕的是“脑内指针飞舞手上却不知道怎么调”有这个函数在每一步操作后看一遍输出指针绕不清楚的问题基本都能当场解决。