简介数据结构与算法是程序员的基石也是计算机类笔试与面试的必考领域。理解时间复杂度与空间复杂度的本质掌握链表反转、二叉树遍历、快速排序、二分查找等高频操作的手写实现是应对有限时间内编码考核的关键。从基础概念出发梳理常见数据结构的必考动作与算法复杂度推导形成一套包含二十个手写模板的复习清单并指出递归爆栈、边界条件等常见陷阱帮助读者将知识转化为可稳定输出的考场能力。1. 计算机类笔试里的数据结构与算法知识点总结为什么值得花一周专门背先讲一个常见翻车现场某同学刷了三百道题上了考场却连一棵二叉树的非递归后序遍历都写不顺最后只留了递归实现的代码在“空间复杂度”追问环节直接崩溃。另一类问题刚好相反——能把红黑树的旋转背得滚瓜烂熟但让他手写一个二分查找却在while (l r)和while (l r)之间来回改浪费了本可以去解大题的十分钟。这两类问题指向同一个事实计算机类考核中的数据结构与算法本质上不是在考“你知道多少概念”而是考“你在有限时间里能否把高频知识点还原成可运行的代码和可解释的结论”。这篇知识点总结不会带你刷上千道题而是把考点收敛成一张检索表、一组必须手写熟练的代码模板、一份避开常见错误的清单。适合两类人刚开始系统复习的新手以及离考核还剩两三周、需要把知识密度压缩到极限的老手。你的目标是学完就能闭上眼睛把链表反转、二叉树层序遍历、快排分区、二分查找这几段核心代码现场写出来——这才叫“掌握”。下文所有内容都围绕一个主轴考什么、怎么背、怎么写、坑在哪。从考点梳理开始再到手写代码最后落到临考模板。2. 把考点梳理成一张检索表考什么、怎么考、怎么答数据结构与算法的复习最怕“什么都看了什么都不深”。市面上很多知识点总结按教材目录平铺顺序表、链表、栈、队列、树、图、排序、查找各占一章每章又是定义、操作、代码、复杂度一整套。问题在于考核不会按教材出题它按“动作”出题。所谓“动作”就是某类数据结构在真实工程和笔试里最常用的那几个操作。你会发现线性表翻来覆去就考插入删除和反转树就考遍历图就考最短路径和拓扑排序。把动作抽出来考点立刻少了一半。2.1 数据结构模块七类对象的必考动作下面这张表是复习时的最小检索集每种数据结构只保留高频动作。旁边标注“必须会手写”或“能口头说清”两个要求避免你在不重要处消耗过多时间。数据结构高频动作典型出题方式手写要求顺序表数组遍历、插入、删除、双指针移动合并有序数组、原地去重必须手写链表单链表反转、快慢指针、删除节点反转链表、找环入口、倒数第K节点必须手写栈入栈出栈、单调栈括号匹配、表达式求值、接雨水必须手写队列入队出队、循环队列层序遍历、滑动窗口最大值必须手写二叉树三种递归遍历、层序、求深度重建二叉树、最近公共祖先必须手写图邻接表、BFS/DFS、拓扑排序、最短路径课程安排、单源最短路径BFS/DFS 必须手写Dijkstra 能写伪代码哈希表冲突处理、装载因子两数之和、LRU 缓存会用语言内置结构即可不手写底层排序和查找是跨数据结构的算法单独放到第 4 章讲。这块复习策略很简单每个对象先花半小时把定义和复杂度写在一张卡上再花一小时把“必须手写”的代码敲三遍。第一遍看着写第二遍合上写第三遍限时写。三天以后这些代码会变成手指记忆考场输出速度比现场推演快得多。2.2 算法模块复杂度、排序、查找、递归复杂度是算法题的“入场券”。很多人只记住 O(n) O(n log n) O(n²) 这个粗略顺序但一遇到具体场景就乱。比如哈希表平均 O(1)、最坏 O(n)为什么还能大量使用因为设计里装载因子和冲突策略把最坏情况压到几乎不出现。再比如快速排序平均 O(n log n)、最坏 O(n²)核心考题问你“什么时候退化成 O(n²)”——答案是每次分区都选到极值作为基准递归深度变成 n。常见复杂度从小到大可以排成一条链O(1) O(log n) O(n) O(n log n) O(n²) O(2ⁿ) O(n!)。笔试时遇到一个陌生算法先看它的主体循环层数再看递归展开的规模基本能估出数量级。嵌套一层循环通常是 O(n) 到 O(n²)取决于内层是否随外层线性变化递归则常涉及 O(log n) 与 O(n log n) 的区别——二分递归是 log n 层每层线性扫描就是 n log n。递归本身是算法模块里的隐藏考点。它不单考斐波那契而是考“递归怎么转迭代”“递归栈溢出怎么办”。这类问题在机考中尤其常见因为系统栈深度有限。处理套路固定能写尾递归的写尾递归不能写的用显式栈模拟。显式栈的自由度更高面试追问时也更占优势。2.3 复习顺序先建立“最小写码集”多数人复习失败不是因为不努力而是顺序不对。一上来就啃图的复杂算法线性表和二叉树还没写熟结果每个知识点都是半生不熟。我一般建议按这条链推进线性表 → 栈与队列 → 二叉树 → 排序 → 查找 → 图。线性和树是基础排序是它们之上的综合应用查找和二分又是一把通用钥匙图则放在最后冲刺。每完成一个阶段要有可量化的产出线性表阶段结束能默写链表反转和有序数组合并二叉树阶段结束能默写三种递归遍历和层序遍历排序阶段结束能默写快排、归并、堆排中至少两种。这个“最小写码集”大约包含二十段代码也就是第 6 章要讲的核心模板。阶段规划建议采用三遍法第一遍理解结构第二遍对着代码逐行讲清每行的作用第三遍合书在白纸上模拟考试写码。三遍之后基本不用再翻教材直接用题来检验。3. 线性结构与树图手写代码的高频考点理论归理论考场上最终看的是手写代码。这一章把第 2 章划定的“必须手写”项目展开给出可直接背诵的代码骨架并解释每段代码里关键的边界处理。3.1 链表反转与环检测三个指针解决的问题链表反转是出现频率极高的一道题因为它能同时考察指针操作和对“引用”的理解。递归思路简单但面试追问时容易被空间复杂度问住迭代法更稳妥。常见做法是用三个指针pre指向已反转部分的前驱cur指向当前待反转节点next暂存下一个节点。def reverse_list(head): pre None cur head while cur: next_node cur.next # 先保存下一个节点防止链表断开后丢失 cur.next pre # 把当前节点的指针指向前一个节点完成反转 pre cur # pre 向后移动 cur next_node # cur 向后移动 return pre # 循环结束时 pre 指向原链表的尾节点即新链表头逻辑说明每次循环只做两件事——把当前节点的next反转然后把两个指针整体后移。关键在于next_node必须最先保存否则执行cur.next pre后原来的下一个节点就找不到了。参数说明函数入参head是原链表头节点返回值为反转后的新链表头空链表和单节点链表直接由循环逻辑覆盖不需要特判。这道题的边界陷阱是返回值很多人写成返回cur但循环结束时cur已经是None正确返回的是pre。环检测的快慢指针是同一个思路的延伸。慢指针每次走一步快指针每次走两步如果链表有环两者必然相遇。def has_cycle(head): slow fast head while fast and fast.next: slow slow.next # 慢指针每次走一步 fast fast.next.next # 快指针每次走两步 if slow is fast: return True return False逻辑说明快慢指针都在环里移动时快指针相对慢指针每次逼近一步所以迟早相遇。快指针循环条件要同时判断fast和fast.next避免空指针异常。3.2 二叉树遍历递归背模板非递归考栈二叉树遍历是“背了不一定考但不背一定会卡”的知识点。递归版三兄弟只有一行核心代码的区别必须形成肌肉记忆非递归版则是栈的典型应用常作为“手写代码”的压轴题。先看递归版先序遍历def preorder(root): if root is None: return visit(root) # 先访问根节点 preorder(root.left) # 再递归左子树 preorder(root.right) # 最后递归右子树逻辑说明递归版之所以容易写是因为系统帮我们维护了调用栈。真正在考场上让代码加速的是先序遍历的显式栈版本因为能直接体现对栈的理解def preorder_iter(root): if root is None: return [] stack [root] result [] while stack: node stack.pop() result.append(node.val) if node.right: stack.append(node.right) # 右子树先入栈左子树后入栈保证左子树先弹出 if node.left: stack.append(node.left) return result逻辑说明栈是后进先出要想先访问左子树就必须让右子树先入栈。这段代码还有一个变体先只沿左路压栈再依次弹出配合visited集合就能处理中序和后序。考试时如果能写出这个栈版本面试官对“非递归理解”的评价通常远高于递归版。层序遍历则用队列每轮循环处理一层的节点def level_order(root): if root is None: return [] from collections import deque queue deque([root]) result [] while queue: level [] for _ in range(len(queue)): # 每轮循环开始前queue 中恰好是当前层所有节点 node queue.popleft() level.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) result.append(level) return result逻辑说明len(queue)必须在进入for循环前确定Python 里range(len(queue))在循环开始时就固定了迭代次数所以能正确切分一层。这个“按层定长”的技巧同时可用在图的 BFS 里比如求最短步数。3.3 图的考场策略邻接表、Dijkstra 与拓扑排序图这章很多学生复习时投入产出比最低。图的算法面很宽但考核真正高频的只有三件事建图方式、BFS/DFS 遍历、拓扑排序与最短路径。建图首选邻接表因为它既能表达稀疏图又方便遍历。graph [[] for _ in range(n)] # n 为节点数 for u, v in edges: graph[u].append(v) # 有向边 u - v逻辑说明graph[i]是节点 i 的邻居列表。无向图加双向边即可带权图把邻居改成(v, weight)元组。邻接矩阵适合稠密图但笔试和机考题目规模通常用邻接表就够。拓扑排序最稳的写法是入度表 BFS也叫 Kahn 算法from collections import deque def topo_sort(n, edges): graph [[] for _ in range(n)] indeg [0] * n for u, v in edges: graph[u].append(v) indeg[v] 1 queue deque([i for i in range(n) if indeg[i] 0]) result [] while queue: u queue.popleft() result.append(u) for v in graph[u]: indeg[v] - 1 if indeg[v] 0: queue.append(v) if len(result) ! n: return [] # 存在环无法完成拓扑排序 return result逻辑说明每次都把当前入度为 0 的节点取出相当于不断剥离没有前置依赖的任务。最终结果长度如果小于节点总数说明图里有环——这是判断“课程安排是否能完成”这类题的核心结论。Dijkstra 算法在笔试中更常以“思想分析”出现比如追问为什么不能处理负权边。手写完整代码量较大机考时间紧时可退化为用优先队列实现的核心循环。务必记住它的贪心前提每次选择距离最近且未确定的节点这个选择一旦确定就不再更新。正因为这个前提负权边会让已确定的最短路径被后续负权更新推翻所以必须用 Bellman-Ford。4. 排序与查找背结论不如推一遍排序和查找在知识点总结里占的篇幅通常最多但真正该背的结论不超过十行。更重要的排序和查找的代码实现以及它们和复杂度的对应关系。这一章把三个必写算法拆开说明边界在哪再用一个对比表收住结论。4.1 快速排序分区函数是失分重灾区快排的平均性能最好也是各大考核中出镜率最高的手写排序。它的核心不是递归主框架而是分区函数partition。分区写不对递归外层再没意义。def partition(arr, low, high): pivot arr[high] # 每次取最后一个元素当基准 i low - 1 # i 指向已处理区段的最后一个元素 for j in range(low, high): if arr[j] pivot: # 小于等于基准的放到左边 i 1 arr[i], arr[j] arr[j], arr[i] arr[i 1], arr[high] arr[high], arr[i 1] # 基准归位 return i 1 # 返回基准最终下标逻辑说明循环里j负责扫描待处理区每当遇到小于等于基准的元素就把i右移并交换实际上是在向左半区累积较小区段。循环结束基准pivot换到i1位置此时基准左侧全部小于等于它右侧全部大于它。参数说明low和high是这一轮处理的左右边界pivot取arr[high]换别的取法会导致i的初始值和交换逻辑变化考试时不要中途更换策略。快排退化到 O(n²) 的本质是每次分区严重失衡。最坏情况发生在基准正好是当前区段的最大或最小值时此时每次只消除一个元素递归深度为 n总比较次数就是 n (n-1) ... 1也就是 O(n²)。4.2 归并排序稳定但吃内存顺手解决逆序对归并排序的优点是稳定缺点是需要额外 O(n) 空间。代码结构非常固定先递归拆后合并。def merge_sort(arr): if len(arr) 1: return arr mid len(arr) // 2 left merge_sort(arr[:mid]) right merge_sort(arr[mid:]) return merge(left, right) def merge(left, right): i j 0 res [] while i len(left) and j len(right): if left[i] right[j]: res.append(left[i]) i 1 else: res.append(right[j]) j 1 res.extend(left[i:]) res.extend(right[j:]) return res逻辑说明合并时left[i] right[j]用了小于等于所以相同元素的相对顺序得以保持这是归并稳定性的来源。临时数组res就是额外空间的去向。归并排序在考题里还有一个高频变体计算逆序对数量。合并时如果left[i] right[j]说明left中从i到末尾的所有元素都比right[j]大逆序数直接加上len(left) - i。一次合并统计一轮所有合并的统计值累加就是答案时间复杂度保持 O(n log n)。4.3 二分查找区间定义是死循环源头二分查找可能是全篇最容易被“觉得会了”的算法。它代码短但边界错法花样多。最常见的错误是循环条件与区间定义不匹配。下面给出一种左闭右闭写法并把返回值收在l上def binary_search(nums, target): l, r 0, len(nums) - 1 # 左闭右闭区间 [l, r] while l r: mid l (r - l) // 2 # 用减法代替 (lr)//2防止整型溢出 if nums[mid] target: return mid elif nums[mid] target: l mid 1 else: r mid - 1 return -1逻辑说明这里的关键是每轮缩区间时都把mid排除在外。因为nums[mid]已经比较过了不需要再留在区间里。如果写l mid或r mid区间可能永远缩不小于是死循环。参数说明nums必须有序且支持下标访问target是目标值返回值为目标下标或 -1。这个模板的变体比如找左边界、右边界都是在nums[mid] target时继续缩半边区间而不是直接返回。排序算法的最终结论整理为下表笔试前直接背它比临时推导稳排序算法平均时间复杂度最好时间复杂度最坏时间复杂度空间复杂度稳定性冒泡排序O(n²)O(n)O(n²)O(1)稳定选择排序O(n²)O(n²)O(n²)O(1)不稳定插入排序O(n²)O(n)O(n²)O(1)稳定快速排序O(n log n)O(n log n)O(n²)O(log n)不稳定归并排序O(n log n)O(n log n)O(n log n)O(n)稳定堆排序O(n log n)O(n log n)O(n log n)O(1)不稳定插入排序的最好 O(n) 对应几乎有序的数据快排最坏 O(n²) 对应每次分区严重失衡堆排虽然最坏也是 O(n log n)但常数较大且不稳定。这三行是面试追问里最喜欢挖的细节。5. 应试避坑算法题做错的三类共性原因这一章写的是复习和模考里反复出现的踩坑记录每条都按“现象 → 原因 → 解决”展开。这些坑不解决知识点总结背得再熟考场上一紧张照样写错。5.1 复杂度背混把快排最坏情况记成 O(n log n)现象被问到“快排最坏时间复杂度是多少”时脱口而出 O(n log n)还补了一句“因为是分治法”。追问“什么情况下变坏”时答不上来。原因只背了平均复杂度没从分治递归的角度推导最坏情形。快排的递归表达式是 T(n) T(左半区) T(右半区) O(n)。平衡分区时每层总比较量是 O(n)递归树深度是 log n所以是 O(n log n)当基准每次都是最小或最大值左右半区严重失衡递归深度变成 n总复杂度变成 O(n²)。解决复习时不要背结论要把递归表达式写一遍。看到任何分治算法先问自己“每一层的工作量是多少、递归深度是多少”。堆排最坏也是 O(n log n) 的原因同理——堆调整操作每次都把问题规模减半不会出现极端失衡所以它最坏情况仍然是 O(n log n)。这两组结论放在一起对比记才不容易混。5.2 手写递归爆栈没有考虑深度限制现象本地测试递归版快排或归并时一切正常到了机考环境用较大规模数据一跑直接抛栈溢出异常或是在递归后序遍历被追问“空间复杂度”时卡壳。原因系统栈帧大小是有限资源递归深度达到数万层就可能溢出。归并排序递归深度是 log n大多安全但链表的递归反转、快排最坏情况下的递归深度都可能是 n超过阈值就崩。更深一层的问题是很多考生把“递归能用”等同于“递归能通过考核”忽略了显式栈和非递归版本的教学意义。解决递归代码写完后顺手问自己“最大深度是多少”。超过几千层的准备一个显式栈版本。比如用栈模拟后序遍历时可以用(node, visited_flag)元组控制访问状态压栈时标记是否已访问过。这一招在机考里能直接把递归爆栈翻车概率降到零。5.3 边界条件写错空输入、单元素、重复元素现象链表反转代码单独看没问题但一遇到head None就报属性错误二分查找在数组只有两个元素时区间收缩不对返回 -1快排在所有元素都相等的输入上死循环。原因很多代码模板是拿“理想输入”推出来的没有做边界防御。链表反转循环里直接访问cur.next如果cur是None自然崩溃快排分区把所有元素都小于等于基准时i会一路走到high如果基准是high则交换后原地归位没问题但换一种基准写法就可能越界。解决给每段核心代码准备“三个测试样例”空输入、单元素输入、全相同元素输入。写代码前先想清楚这三点很多边界问题会自然暴露。链表反转在函数开头加if head is None或if head.next is None特判二分查找让l和r的更新总是至少收缩一个下标快排则在递归前判断low high避免对空区间再分区。这算是最低成本的后悔药一次写好节省考场上反复调试的十分钟。6. 临考前三天把知识点收成二十个手写模板知识点总结类复习资料最大的问题不是内容不够而是内容太散。理想状态是考前三天不再翻教材只拿一张 A4 纸按固定顺序把二十个模板手写一遍。写不出来的就是当天需要重点补的地方。这个习惯我保持了很多年每次考核前都靠它把焦虑转化成具体的行动量。二十个模板可以按类别固定下来链表反转、快慢指针找中间节点、链表删除节点、栈实现队列、队列实现栈、单调栈模板、循环队列、二叉树递归先序、递归中序、递归后序、非递归先序、层序遍历、二叉树最大深度、判断平衡二叉树、快排、归并排序、堆排序的堆调整过程、二分查找、拓扑排序、Dijkstra 核心循环。这些模板覆盖了至少七成高频手写题。验证方式不是“看一遍觉得会了”而是限时手写。我会给自己定一个规则每个模板 10 分钟内写完写完不要在纸上检查直接默念逻辑推演三遍。第一遍看这行代码在输入是什么状态第二遍看循环结束条件是否保证收敛第三遍看返回值和边界特判。三遍下来如果没问题这个模板才算过。如果时间只剩三天可以进一步压成“三表一码”复杂度表、稳定性表、栈与队列操作表、二分模板码。这三张表覆盖几乎所有理论选择题一份二分词解决所有手写题。模板不是死记硬背而是背“结构骨架”比如快排记住“分区、递归、基准归位”三个节点其他细节由节点自然展开。最后说一个比较私人的习惯每次手写二分查找之前我会先在草稿纸上写一行注释“区间 [l, r]排除 mid”然后才开始写循环。这行注释看起来多余却能防止在最紧张的十分钟里思路漂移。类似的小动作可以延伸到链表反转前写“pre/cur/next”层序遍历前写“当前层长度”。一句话注释换来稳定输出值得养成。算法知识点总结到最后比天赋更重要的是重复和复盘。二十个模板每天过一遍每条踩坑记录考前再看一眼考场上大概率不会再犯同类错误。希望这套方法帮到你也希望你在真实考场上能把每个模板写成一气呵成的肌肉记忆。本文还有配套的精品资源点击获取