Python面试30分钟突击掌握-LeetCode3-Linked list

如果你正在准备 Python 开发面试链表是必须掌握的一类题。它看起来不像数组那样直观但只要掌握几个固定套路拿分会非常稳定。这一篇延续前两篇的突击风格少而精只练最经典、最常考、最容易被追问的两题。为什么 Linked List 高频出现面试官喜欢链表题不是因为它“难”而是因为它能快速区分候选人的基本功是否真正理解指针/引用关系能否在不借助额外数组的情况下原地操作能否稳定处理None、空链表、单节点等边界写代码时是否清楚每一步指针移动。如果你只有 30 分钟建议优先吃透这两题Reverse Linked ListMerge Two Sorted Lists它们分别覆盖两种核心技巧指针反转迭代 递归dummy 虚拟头节点 双指针拼接今天的突击目标只要做到下面四点这一篇就算学到位了能手写并讲清楚Reverse Linked List的迭代与递归能说清Merge Two Sorted Lists里dummy的价值能在讲解时明确时间/空间复杂度能主动指出易错点尤其是指针断链问题。题目一Reverse Linked List反转链表题目描述给定单链表头节点head将链表反转并返回反转后的头节点。示例输入[1,2,3,4,5]输出[5,4,3,2,1]输入[1,2]输出[2,1]输入[]输出[]面试中的思考路径这题的 follow-up 常问“你能分别用迭代和递归实现吗”解法一迭代首选最稳迭代核心是三个指针变量prev当前节点反转后要指向的前驱curr当前处理节点nxt提前保存curr.next防止断链后找不到后续节点。Python 参考实现迭代fromtypingimportOptionalclassSolution:defreverseList(self,head:Optional[ListNode])-Optional[ListNode]:prevNonecurrheadwhilecurr:nxtcurr.nextcurr.nextprev prevcurr currnxtreturnprev解法二递归面试加分递归写法的关键点是递归到底到尾节点后尾节点会成为新头回溯时把后一个节点的next指回当前节点。Python 参考实现递归fromtypingimportOptionalclassSolution:defreverseList(self,head:Optional[ListNode])-Optional[ListNode]:ifheadisNoneorhead.nextisNone:returnhead new_headself.reverseList(head.next)head.next.nexthead head.nextNonereturnnew_head递归易错点很多人会写成new_head.next head这种写法通常是不对的因为new_head指向的是“新头”并不总是“当前节点的下一个节点”。正确做法必须基于当前层关系写成head.next.next headhead.next None这样才能保证每一层回溯都正确翻转并且不会形成环。和斐波那契递归有什么区别这点面试里讲出来很加分斐波那契常见写法是分叉递归一个函数拆成两个子问题有大量重复计算反转链表是单链递归每层只递归一次没有分叉爆炸因此链表递归更接近“沿链到底再回溯改指针”的过程逻辑更线性。复杂度分析迭代时间O(n)空间O(1)递归时间O(n)空间O(n)递归调用栈。题目二Merge Two Sorted Lists合并两个有序链表题目描述给定两个升序链表list1和list2将它们合并为一个新的升序链表并返回头节点。要求通过“拼接原节点”的方式完成不是新建值数组再重建链表。示例输入list1[1,2,4], list2[1,3,4]输出[1,1,2,3,4,4]输入list1[], list2[]输出[]输入list1[], list2[0]输出[0]面试中的思考路径这题最稳定写法是dummy curdummy是虚拟头节点避免处理“第一个节点到底挂谁”的分支复杂度cur始终指向合并链表的尾部每次比较list1.val与list2.val把较小节点接到cur.next某一条链表走完后直接把另一条剩余部分接上。Python 参考实现fromtypingimportOptionalclassSolution:defmergeTwoLists(self,list1:Optional[ListNode],list2:Optional[ListNode])-Optional[ListNode]:dummyListNode()curdummywhilelist1andlist2:iflist1.vallist2.val:cur.nextlist1 list1list1.nextelse:cur.nextlist2 list2list2.nextcurcur.nextcur.nextlist1iflist1elselist2returndummy.next复杂度分析时间复杂度O(mn)两个链表各走一遍空间复杂度O(1)只使用常数额外指针。面试易错点不用dummy导致头节点处理写出很多 if-else比较后忘记移动cur循环结束后忘记拼接剩余链表误新建大量节点偏离“拼接原链表节点”的意图。30 分钟高效练习法Linked List 版按这个节奏走效率很高5 分钟先口述两题指针变化过程10 分钟手写reverseList迭代 递归10 分钟手写mergeTwoLists重点练dummy5 分钟不看代码复述复杂度和易错点。链表题最怕“看懂了但写不对”所以一定要手写。面试表达模板可直接套用你可以这样说这题我会优先考虑指针原地操作避免不必要的额外空间。如果涉及链表拼接我会引入 dummy 节点统一处理头节点逻辑减少分支。在实现上我会先保证不断链再改指向最后移动指针。复杂度方面目标通常是线性时间额外空间尽量保持常数级。这段话很适合链表题开场能快速体现你的工程化思维。小结Linked List 的关键不是“记住答案”而是形成稳定的指针操作习惯。把Reverse Linked List和Merge Two Sorted Lists吃透后你会对链表题建立很强的控制感。面试前请至少达到这个标准迭代反转和递归反转都能默写能解释为什么head.next.next head是关键dummy cur写法一遍过复杂度和边界条件能清楚表达。下一篇可以继续进入Trees把链表和树这两类“指针结构”连起来面试中的数据结构题会更稳。支持一下如果这篇对你有帮助欢迎点赞、收藏、关注。 有余力的话欢迎打赏支持我会更新得更快。