把“回归数”和“合并链表”放到一篇文章里聊听起来有点像算法题拼盘但如果真拿这两道题去面试、去带新人、去刷题库你会发现它们背后暴露的是同一个问题边界条件处理得干不干净直接决定了代码是“能跑”还是“能看”。回归数是典型的数字拆解 暴力枚举题合并链表是典型的引用操作 边界判断题。前者考你有没有数学直觉后者考你有没有链表思维。这篇文章我不打算只给标准答案而是把两道题从原理、实现、剪枝、踩坑到面试表现全部拆开把我实际写代码和面试别人时反复遇到的问题都放进来。1. 回归数并不是昵称这个经典数学概念的正确打开方式1.1 从水仙花数说起回归数到底指什么国内学编程的人几乎都听说过水仙花数经典题目“打印所有的水仙花数”从C语言课本一路传到Python入门课。但很多人不知道水仙花数只是回归数的特例。回归数英文一般叫Armstrong Number或Narcissistic Number也叫自恋数、自幂数。定义很简单一个n位的正整数它的每一位数字的n次方之和恰好等于它本身。写成公式就是N d1ⁿ d2ⁿ ... dnⁿ其中N有n位数字di是每一位上的数字。举个例子153 1³ 5³ 3³ 1 125 27所以153是一个3位回归数。370、371、407也都满足这个条件所以3位回归数一共有4个这4个就是我们常说的水仙花数。为什么叫“回归”因为数字在“自指”的意义上回到了自身——你把它拆开再组合回来的还是它本身。这个命名虽然比“水仙花”少点文学味道但在数学资料里更通用尤其在英文文献和早期国内算法教材里很常见。1.2 回归数的数学本质自幂、位数与枚举范围回归数的核心在于“位数”和“幂次”绑定。也就是说判断一个数是不是回归数不能只看数字和幂次必须先确定它有多少位。这个“位数”决定了你要用几次方。很多新手第一次写这个程序时会本能地以为“把一个数每一位的数字取出来做三次方因为常见的是三位水仙花数然后求和再判断是否相等”。如果题目固定输入范围是100到999这样没问题但如果让你判断一个四位数或者打印所有三位数以内的回归数这个“硬编码幂次”的做法就会出错。回归数从1到9都在这个定义范围里——一位数的1次方就是它本身所以0到9都是一位回归数部分题目要求正整数时会排除0。但常见的竞赛和面试题往往只关注三位或四位以上的数因为更有辨识度。1.3 一张小表把低位数回归数看全面我习惯在写任何幂次相关的算法前先列出前几位的预期值用来验证程序输出是否完整、是否有遗漏。位数n范围回归数10~90, 1, 2, 3, 4, 5, 6, 7, 8, 9210~99无3100~999153, 370, 371, 40741000~99991634, 8208, 9474510000~9999954748, 92727, 930846100000~999999548834我每次写完暴力实现都会拿这张表去跑一遍能对上就说明拆位和幂运算的基本逻辑没问题。特别是**“两位数没有回归数”这个反直觉结论**常常能帮你在写完代码后第一时间发现计算错误——如果程序把两位数的某个数判为回归数那一定是小学数学没过关。2. 回归数的暴力求解与剪枝代码怎么写才地道2.1 最直接的枚举实现既然定义了“枚举 判断”那最简单可靠的做法就是从10的n-1次方枚举到10的n次方减1每个数都做一次拆位和求和判断。先把最朴素、最不容易错的写法写出来再考虑优化。以Python为例def is_narcissistic(num: int, power: int) - bool: total 0 temp num while temp 0: digit temp % 10 total digit ** power temp // 10 return total num def find_armstrong_by_range(n: int): result [] start 10 ** (n - 1) end 10 ** n for num in range(start, end): if is_narcissistic(num, n): result.append(num) return result print(find_armstrong_by_range(3)) # [153, 370, 371, 407]这段代码的逻辑顺序很重要先确定幂次n再枚举范围内每个数最后按位拆解并累加幂和。整个思路用一个while循环拆位用内建的**做幂运算足够应付n小于7的情况。不过这段代码有一个可以预见的性能隐患digit ** power在每个数上会执行n次而幂运算本身是有成本的。当n8、n9时Python暴力枚举的时间会肉眼可见地变慢。面试的时候如果只写到这里基本上算“勉强跑通”离“有条理”还差一步。2.2 拆分数字的那些细节坑拆位是最容易写出隐蔽bug的地方。我见过不少人在拆位时少写temp // 10导致while循环永远跳不出去也有人把temp和num混用导致拿修改后的值去和原数比较。拆位的标准步骤其实一句话就能说清楚用temp保存原数不能直接修改num每次循环用temp % 10拿到当前最后一位累加该位的power次幂用temp // 10去掉最后一位当temp变为0时停止。这段逻辑不只在回归数里出现所有“提取一个整数每一位”的问题——回文数、统计数字出现次数、数字反转——用的都是同一套东西。这个基本功练不好后面做字符串和进制转换也会受影响。另外有个容易被忽略的细节n1时range(10**(1-1), 10**1)是range(1, 10)会漏掉0。如果题目要求包含0需要单独处理如果不要求那正好。实际做题时建议先看清题目有没有说“正整数”我见过不少人因为多输出了一个0被误判。2.3 剪枝思路减少幂运算次数暴力枚举最大的问题是指数级的复杂度。10^n范围随着n增大是指数膨胀的n10时已经要遍历90亿个数逐个数算幂和谁都顶不住。真正的优化思路不是“每个数少算点”而是不要基于数来枚举改成基于数字组合来枚举。回归数的本质是它的值只取决于每一位上的数字是什么跟数字的排列顺序无关。也就是说判断一个数是不是回归数只看数字集合就够了。那么我们可以反过来思考一个n位数每一位只能是0~9我先不关心顺序直接枚举“每个数字出现几次”的组合用这些出现次数算出“数字幂次方的加权和”再判断这个加权和的位数以及它每一位数字的出现次数是否正好和当前枚举的组合一致。这个方法通常被称作“组合枚举法”能把n10到n20的回归数都算出来普通暴力法跑到n8、9可能就要等很久了。不过这里我不打算直接写完整实现因为对于绝大多数用来练手或者面试的场景暴力法已经足够。真正要理解的是“为什么可以剪枝”——因为枚举空间从数字变成了计数组合从90亿个数变成了组合数C(n9, 9)级别的方案这才是数量级的差异。2.4 哈希判重与题目变体组合枚举法还有一个配套问题同一个“数字出现次数组合”可能对应多个排列但最终判断出来的回归数只有一个数字本身。比如数字集合 {1, 3, 5} 的排列有153、315、135等多种但满足回归数的只有153。因此用组合枚举行进时需要把算出来的结果放到集合中避免重复输出。顺带一提回归数的题目经常以变体的形式出现“打印n位以内的所有自幂数”这个需要对每个位数都跑一遍“求第K个回归数”这个通常需要先生成大量回归数再排序“判断一个数是不是回归数”这个最简单不涉及枚举只需要按位拆解。我在实际练习时建议按“判断 → 枚举 → 组合优化”的三级跳去掌握它每一步都能解决一类已知问题。不要一上来就追求最优解那样反而容易在各种剪枝细节里把自己绕晕。3. 合并链表前先建立链表直觉哑结点和引用传递3.1 链表和数组的本质差别聊完回归数我们把视线从数字转到链表。合并两个有序链表是链表题里最基础也最经典的一道LeetCode编号21标题就叫Merge Two Sorted Lists。链表和数组最大的不同在于数组靠下标访问元素链表靠next指针串联节点。很多从数组思维转过来的新手写链表题时会下意识地想要“第几个节点”然后发现链表根本没有随机访问能力。数组合并两个有序序列你可以用双指针从两头的数组头开始移动因为数组天然支持arr[i]这种O(1)取值的操作。链表也能用双指针但操作对象不是“下标”而是节点引用。你要做的不是记录位置而是不断把当前指针指向的那个节点接到新链表上。我这里直接用Java的单链表节点定义来做演示因为国内面试用Java或C写链表题的频率非常高public class ListNode { int val; ListNode next; ListNode() {} ListNode(int val) { this.val val; } ListNode(int val, ListNode next) { this.val val; this.next next; } }链表的节点里同时存了“值”和“下一个节点的引用”。这个“引用”就是链表的心跳——你改变cur.next的指向就相当于改变了整条链的走向。3.2 合并有序链表的题目要求与边界题目很直观给定两个升序链表 l1 和 l2把它们合并成一个新的升序链表并返回。比如输入l1 [1, 2, 4]l2 [1, 3, 4]输出[1, 1, 2, 3, 4, 4]看起来很简单但它有一堆边界条件专门等着不细心的人l1为空l2不为空——直接返回l2l2为空l1不为空——直接返回l1两个都为空——返回null两个链表长度不一致——短的那条走完之后直接把剩下那条剩余部分接上两个链表包含大量重复值——用还是决定了稳定性和输出顺序。第5点尤其容易被忽略。如果两个链表的节点值相等你选择“优先取l1的节点”还是“优先取l2的节点”这取决于你用还是。两种写法都能得到有序结果但面试官如果追问“相等元素谁在前”你最好能明确说出自己的处理策略。3.3 哑结点为什么能省一半判断链表题里最经典的技巧之一就是哑结点dummy node。所谓哑结点就是自己new一个不参与实际数据的头结点让cur指针从它开始向后串接真正的结果节点。为什么需要它因为如果你不用哑结点就要先判断“结果链表的头结点从哪来”然后需要单独处理第一次插入节点的情况。不少人会在这一步写出一堆if (result null)之类的判断代码又长又容易出错。用了哑结点之后所有插入操作都统一变成了cur.next ...和cur cur.next头结点由dummy.next在最后一步取出来即可。这相当于把“初始化链表头”和“插入所有节点”两件事解耦了代码的可读性和正确率都会上一个台阶。public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode dummy new ListNode(0); ListNode cur dummy; while (l1 ! null l2 ! null) { if (l1.val l2.val) { cur.next l1; l1 l1.next; } else { cur.next l2; l2 l2.next; } cur cur.next; } cur.next (l1 ! null) ? l1 : l2; return dummy.next; }注意看一次完整的迭代只做了三件事——比较两个头节点的值把较小的那个接上cur然后移动对应链表的指针。当其中一个链表耗尽时直接把另一个链表的剩余部分整体挂在cur后面因为剩下的部分已经是有序的不需要再做任何比较。4. 合并链表的迭代与递归实现两种写法的取舍4.1 迭代写法稳定与内存占用上面那段代码就是标准的迭代解法。它的优点是空间复杂度是O(1)——除了几个指针外没有额外创建新的节点所有操作都是对原有节点的重新指向。时间复杂度是O(mn)m和n分别是两个链表的长度。最坏情况下要比较完全部的节点所以是线性时间。这个复杂度已经是最好的写法了因为合并必须“看过”所有节点才能保证有序。迭代写法在实际工程中更受青睐因为它调用栈浅、不易触发栈溢出、也不会改变原有链表的内存布局。如果你在做代码Review看到别人用迭代法合并链表我会觉得这是最稳的实现。4.2 递归写法简洁但要注意调用栈递归写法的经典实现同样非常短思路也不难理解public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if (l1 null) return l2; if (l2 null) return l1; if (l1.val l2.val) { l1.next mergeTwoLists(l1.next, l2); return l1; } else { l2.next mergeTwoLists(l1, l2.next); return l2; } }递归的核心是“把大问题缩小”合并 l1 和 l2等价于“取走当前更小的头节点然后继续合并剩下两个链表”。“取走头节点”后被递归函数处理的是剩余部分子问题和原问题结构完全一致这就是递归能生效的原因。但递归有个代价每次递归调用都会在Java虚拟机栈上开辟新的栈帧。如果链表特别长比如有十万个节点递归深度可能达到十万层Java的默认栈大小通常不够用会出现StackOverflowError。所以面试时写递归解法最好主动跟上几句说明“在数据量较小或面试场景下完全没问题但如果链表很长迭代法更安全。”这句话本身就是加分项因为你展示了对自己代码边界情况的理解。4.3 时间复杂度与空间复杂度对比我把两种解法并排放一起对比后面复习时可以直接对照维度迭代递归时间复杂度O(mn)O(mn)空间复杂度O(1)O(mn)栈帧开销编码复杂度低但注意哑结点极低几行搞定栈溢出风险无有长链时明显工程场景更推荐适合理解递归思想我个人的建议是面试时先讲递归因为它逻辑清晰、代码短适合在有限时间内证明你理解了“归约”思想然后再补一句迭代写法展示你知道工程上的取舍。不要一上来就写迭代写完之后再去解释递归思路反而要绕一大圈。5. 两个题目背后相通的三种能力边界感、拆解思维、复杂度嗅觉5.1 边界条件即第一生产力回归数和合并链表一道是纯数学计算一道是链表结构它们放在一起看最明显共通的点是边界条件决定生死。回归数里你忘处理一位数的0输出结果就和标准答案差一个你用还是在遇到重复数字时会改变输出集合你把temp和num搞混判断就会失真。合并链表里你不处理空链表就会出现空指针异常你不用哑结点就要单独写一段初始化逻辑你忘记剩余链表的拼接结果就少一半节点。这些边界条件每一个都看着不起眼但都是真实代码里最容易挂的地方。我对新人的建议永远是写代码前先花30秒在纸上列一遍输入可能出现的极端情况这比多写50行防御性代码更有效。5.2 拆解思维数字拆位与链表拆节点第二点相通的是“拆解”的思路。回归数的拆解是面向“数字位”的十进制的每一位通过除法和取模逐层分离。合并链表的拆解是面向“节点”的每一步只处理一个节点把它从原链表中摘下来再挂到新链上去。这两种拆解看似不同本质上都是一种“局部处理 指针移动”的模式。数字拆位用temp // 10移动“指针”链表拆节点用l1 l1.next移动“指针”。能把这两个过程想明白说明你对“如何把一个大问题反复拆成同构的小问题”有直觉。这种拆解思维在做更复杂的题时会反复用到比如反转链表是“摘一个头 反转剩余”、数字倒序输出是“取末位 递归处理剩余位”。所以说学会这两个基础题远不止会做两道题那么简单。5.3 复杂度嗅觉暴力解法的天花板在哪里第三个相通点在于复杂度嗅觉。回归数的暴力枚举是O(10ⁿ·n)这个复杂度随着位数增加几乎是灾难级的合并链表的迭代是O(mn)递归是O(mn)时间 O(mn)空间。两者都涉及“暴力解法可行但收益有限”的权衡。我对复杂度嗅觉的定义很直白拿到一道题先能估算出暴力做法会不会崩再判断自己要不要写优化。能算出暴力解法的时间复杂度是及格线能说出在什么规模下必须优化是加分线能在面试中为了写更稳妥的代码而自愿放弃更简洁但更耗空间的写法则是经验线。回归数和合并链表恰好是一对很好的练手题——前者让你体会“暴力枚举在指数面前有多无力”后者让你体会“链表题的空间开销和递归深度问题”。把这两道题练透复杂度嗅觉会明显提升。6. 实测经验与面试建议这些坑我踩过你别再踩了6.1 回归数题目的三个常见误判先说说我在写回归数时踩过以及看身边人反复踩的三个坑。第一个坑是“幂次定死”。很多人看到水仙花数就写digit ** 3题目要求“n位以内所有回归数”时直接查不出来。幂次必须和位数一致这是定义本身的要求。第二个坑是“漏掉0”。n1时0满足定义但不少题目要求“正整数”。写代码前把题目多读两遍或者主动跟面试官确认范围是最稳妥的做法。第三个坑是“拿浮点库做整数幂”。Python的math.pow(2, 3)会返回浮点数在数字很大时会有精度问题。虽然三位数可能看不出来但如果你去计算十位以上的幂和浮点误差会造成最后的相等判断出现偶然的false。尽量用整数幂运算或自写快速幂。6.2 链表合并题目的考场细节链表合并虽然简单但面试中的“隐性评分点”非常多。我面试别人时最看重的一点是你会不会在写完解法后主动去测用例。很多候选人写代码飞快但我请他用一个“l1为空、l2非空”的例子走一遍程序时他就愣住了。这说明他的代码从来没有被基站式的边界测试检验过。另外一个细节是很多人会把两个链表的指针搞混。比如在迭代里把l1 l1.next写成了cur l1.next这会导致游标指针直接跳到下一个节点而不是前进一步整个链表结构就乱了。链表题里的变量命名和目标一定要在写之前想清楚。还有一个高频考点是“为什么不用额外数组”。有些人会用ArrayList把两个链表读出来排序再建新链表功能上没问题但空间复杂度和工程习惯都不好。这个问题其实是在考察你有没有“引用重连”这种链表原生的思维方式。6.3 对新手友好的学习路径结合我自己的学习过程给刚开始刷这两类题的新手一个路径参考先用暴力枚举法写出三位回归数的代码记住“拆位 幂和 判等”的套路把枚举范围改成“任意n位”了解幂次必须随位数变化再尝试用组合枚举的思想别看完整题解先自己想想“可不可以不按数字枚举”链表先手动画一遍“把两个链表节点串起来”的过程再写迭代迭代跑通后再写递归注意递归出口和返回值分别写几个边界测试用例包括空链表、不等长链表、全部重复值链表。这套路径其实就是“先暴力建立正确性认知再优化建立复杂度认知最后用边界用例建立工程认知”的过程。我不建议新人上来就背最优解那样表面会写但换一道变体题很容易露馅。最后说点我个人在实际写代码和带人时越来越强烈的感受回归数和合并链表都是那种“看答案三分钟自己写三小时”的题目。它们不靠复杂的数据结构不靠高深的数学定理靠的就是你对程序在边界状况下行为的精确预判。能把这种小题目写得干净利落比会背十道难题的答案更有价值。如果你现在正好卡在“看懂了但自己写不对”的阶段别急把这两道题按我自己上面说的流程多练几次——先去判断边界再去实现逻辑最后回头再看复杂度。我相信你练完这两道题之后对数字操作和链表操作的理解都会上一个大台阶。
