做了这么多年技术面试官也带过不少新人我发现一个挺有意思的现象像“回归数”和“合并链表”这种题目看起来一个偏数学一个偏数据结构风马牛不相及但真正能快速、稳健地把它们写对的人代码功底通常都不差。回归数考的是你对数字本质的理解和位运算拆解的熟练度合并链表考的是指针操作和边界条件的敏感度。这两道题覆盖了算法面试里最核心的两个基本功拆解问题和处理边界。花一个下午把这两个题吃透比盲目刷二十道简单题都管用。这篇文章想跟你聊聊这两道题背后真正值得关注的东西回归数怎么判断最高效、合并链表为什么递归和迭代两种写法都要会、以及实操里那些一不小心就踩进去的坑。不管你是准备面试的在校生还是想补补基本功的初级开发这篇内容应该都能给你点实在的参考。1. 项目概述两个看似不相干的算法题考的其实是同一件事1.1 回归数是什么回归数也叫水仙花数、阿姆斯特朗数简单说就是一个 n 位数它的每个位上的数字的 n 次幂之和等于它本身。最经典的例子是 153153 1³ 5³ 3³ 1 125 27。三位水仙花数只有四个153、370、371、407。这个概念本身不难但真正写代码的时候有个特别容易错的点幂次是“数字的位数”不是固定的 3。很多初学者把三位数做出来了换成四位数 1634 就不知道怎么处理或者干脆写死成三次方这就是没抓住问题的本质。1.2 为什么把这两个题放在一起回归数和合并链表看起来没有任何关系但它们在算法训练里的位置很像都是“小而不简单”的题目。回归数考察你能否把一个复杂判断拆成“位分解 幂次计算 累加比较”三个干净的步骤合并链表考察你能否在多个指针移动时不丢失引用、不产生死循环。我面试候选人的时候如果时间只够写两道题经常就选这两个。回归数能不能快速做出来能看出一个人的数学抽象能力合并链表能不能处理各种边界能看出一位工程师写生产代码时细不细心。这两个题都通过了基本可以确认基础是扎实的。2. 回归数数学判定与暴力解法拆解2.1 位分解的三种写法判断一个数是不是回归数第一步永远是“拿到每一位的数字”。这一步看着简单写起来细节还挺多的。第一种写法是转字符串。把数字转成字符串然后遍历每个字符再转回数字参与计算。优点是代码极短几乎不可能写错。缺点是需要额外的字符串空间而且有些面试官会觉得你绕过了“数学”的部分。第二种写法是数学取余法也是最推荐的做法。核心就一句话循环里不断对 10 取余拿到个位然后整除 10 把数字缩短一位。def is_armstrong(num: int) - bool: if num 0: return False original num n len(str(num)) total 0 while num 0: digit num % 10 total digit ** n num // 10 return total original这段代码里有几个值得注意的点先保存原始值因为循环会修改 num位数 n 要先算好我见过有人在循环里每次调用 len(str(num))位数越算越少结果整个判断全错最后返回的是 total 和 original 的比较不是和 num 比较这个也是常见的低级错误。第三种写法是递归位分解。本质和取余法一样但递归式能让你在更复杂的场景里复用逻辑。def sum_of_powers(num: int, n: int) - int: if num 0: return 0 return (num % 10) ** n sum_of_powers(num // 10, n)递归写法的优势是代码很“数学”读起来像公式但如果递归深度控制不好或者没有退出条件调试起来就比较痛苦。对这种简单场景我还是更推荐循环。2.2 幂次计算的优化与边界位数不多的时候直接digit ** n一点问题都没有。但如果题目扩展到让你找 10 位甚至 20 位的回归数重复计算幂的开销就得上来了。一个非常实用的优化是预计算 0 到 9 的 n 次幂存到一个数组里后面直接用索引取值。powers [i ** n for i in range(10)] total powers[digit]这个优化能省掉大量重复的乘方运算尤其当你需要在一个很大的区间里逐个判断时效果非常明显。从原理上说这是典型的“空间换时间”也符合算法设计里“预处理”这个通用思路。边界情况也要留意。0 和 1 这种个位数按定义 n10¹ 01¹ 1它们都是回归数。如果题目要求“正整数”那 0 就不算如果只说“数字” 0 就要考虑进去。负数直接排除负数不可能是回归数。另外一个隐藏的边界是“原数太大了幂次累加会不会溢出”。Python 不用考虑这个问题但如果你用 C 或 Java 写建议用 long 类型别用 int。2.3 暴力解法的复杂度与效果判断一个数是否为回归数时间复杂度是 O(n)n 是数字位数其实也就是 O(log x)这里的 x 是数字本身。因为每循环一次数字除以 10循环次数就是十进制位数。如果要在某个区间内找出所有回归数暴力做法就是遍历区间内每个数逐个调用判断函数。比如找三位数里的所有回归数从 100 遍历到 999总共 900 次判断耗时可以忽略不计。找五位数就是 90000 次也还能接受。当你需要找十位数以上的回归数时暴力遍历就非常痛苦了因为 10 位数的范围是 10 亿到 99 亿接近 90 亿次判断。这种场景就不能再暴力得用组合枚举的思路预先确定数字出现的次数组合计算幂次和再检查结果是否满足位数和数字组成。这是进阶玩法作为扩展了解就好现阶段先把单个数判断写对写稳。3. 合并链表从迭代到递归的完整思路3.1 题意与前置约定合并链表是 LeetCode 第 21 题也是在真实面试里出场率极高的一道题。题目描述很简短给定两个升序链表 l1 和 l2把它们合并成一个新的升序链表并返回。这里有几个默认约定要先确认清楚。第一链表节点只有 val 和 next 两个字段。第二输入链表是升序的但不保证长度相同。第三“合并”不意味着创建新节点通常的做法是复用原有的节点调整它们的 next 指向。这是面试时的一个讨巧点你可以先跟面试官确认“是否可以原地修改原链表”绝大多数情况下对方都会同意而且会觉得你考虑问题周全。在动手写代码之前我还建议你先在纸上画一下链表的结构。两个指针分别指向两个链表的头节点比较它们的值值小的那个节点作为合并后链表的当前节点然后指针向后移动一位。这个过程特别像“拉链”慢慢拉上非常直观。3.2 迭代法哨兵节点是头号功臣迭代法是最容易理解、也最不容易出错的写法。核心技巧是用一个哨兵节点dummy node来避免处理“头节点为空”的特殊情况。class ListNode: def __init__(self, val0, nextNone): self.val val self.next next def merge_two_lists_iterative(l1: ListNode, l2: ListNode) - ListNode: dummy ListNode() cur dummy while l1 and l2: if l1.val l2.val: cur.next l1 l1 l1.next else: cur.next l2 l2 l2.next cur cur.next if l1: cur.next l1 if l2: cur.next l2 return dummy.next这段代码我写出来也就十行左右但里面藏着三个特别重要的细节。第一个是哨兵节点。如果不引入 dummy第一次循环时 cur 到底指向谁你需要单独处理 l1 和 l2 都不为空时的首个节点选择然后把 cur 指向它后面的逻辑再进入循环。这样写完全没问题但代码会更啰嗦而且容易在“开头处理”这个位置出错。dummy 节点的作用就是让循环体从第一次迭代开始就统一逻辑最后返回 dummy.next 就是合并后的头节点省心。第二个是if l1.val l2.val里的“小于等于”。这个取等号很关键。当两个值相等时优先取 l1 的节点能保证合并过程是“稳定”的。虽然本题对稳定性没有要求但这是链表排序、归并排序这类场景里的基本素养养成习惯没坏处。第三个是循环结束后还有残余链表的处理。循环条件是while l1 and l2意味着一旦有一个链表走完循环就停了。但另一个链表可能还有一串节点它们本来就是有序的所以直接让 cur.next 指向剩余链表的头节点就行。很多新手在这里会写一个 while 循环去遍历剩下的节点一个一个接进去纯属多此一举代码又长又容易错。3.3 递归法一行代码的背后是栈递归法的代码极其简洁初看会觉得惊艳但理解起来需要一点栈的知识。def merge_two_lists_recursive(l1: ListNode, l2: ListNode) - ListNode: if not l1: return l2 if not l2: return l1 if l1.val l2.val: l1.next merge_two_lists_recursive(l1.next, l2) return l1 else: l2.next merge_two_lists_recursive(l1, l2.next) return l2这个递归的核心思路是每次只比较两个链表的头节点值小的那个节点就是合并后链表的头节点它的 next 指向“剩余部分合并的结果”而剩余部分的合并交给递归去处理。递归的终止条件是 l1 或 l2 为空此时直接返回另一个链表因为剩下的一整串都是有序的不需要再处理。从时间复杂度和空间复杂度来看迭代法空间 O(1)递归法因为每次递归调用都会占用栈空间最坏情况下要处理 mn 个节点空间复杂度是 O(mn)。如果链表的长度有几十万递归就会栈溢出所以生产环境里我更偏向迭代法。但面试的时候递归法这种“一行核心逻辑”的写法非常加分它说明你理解了递归的本质是“把大问题拆成同样结构的子问题”。曾经有个粉丝问我为什么递归代码这么短想不出来怎么办。我的建议是不要一上来就想递归先用迭代把思路理通然后对照着看递归的实现。你会发现在迭代里“当前处理完接下来怎么办”的地方就是递归里调用自己的位置。想通了这一步递归就不再是玄学。3.4 时间复杂度分析迭代和递归的时间复杂度都是 O(mn)m 和 n 分别是两个链表的长度。理由是合并过程中每个节点最多被比较一次、被链接一次不存在重复扫描。这一点也是面试官常问的你要能说清楚为什么不是 O(m*n)。空间复杂度上迭代法 O(1)只用常数个指针递归法 O(mn)主要是调用栈的开销。如果你在简历上写了“熟悉常用数据结构”这两个复杂度的对比一定要张口就来。4. 变体拓展从标准题到进阶题的思维模型4.1 回归数的范围拓展从三位到任意位数经典的“水仙花数”通常指三位数但完整的回归数定义适合任意位数。如果你想找出所有三位回归数可以直接遍历 100 到 999。def find_armstrong_three_digit(): res [] for num in range(100, 1000): if is_armstrong(num): res.append(num) return res输出结果是 [153, 370, 371, 407]。四位回归数有 1634、8208、9474。五位有 54748、92727、93084。如果测试用例刚好卡在这些数字附近你的代码就基本没问题。更进一步如果你想找“指定位数内所有回归数”可以从 10^(n-1) 遍历到 10^n - 1。代码上只需要把判断函数里的位数计算改成 n别的逻辑不需要动。但如前所说位数大了之后暴力法会超时这时候就需要组合枚举的进阶思路这篇不展开有兴趣可以自己去搜“Armstrong number 生成算法”相关的资料。4.2 链表操作的下一个台阶合并 K 个有序链表合并两个有序链表会了合并 K 个有序链表就是水到渠成的进阶题。LeetCode 第 23 题题干是一组有序链表要把它们全部合并成一个有序链表。最简单的做法是“两两合并”先合并前两个再把结果和第三个合并以此类推。这种方法写起来最快时间复杂度是 O(k²n)其中 k 是链表数量n 是每个链表的平均长度因为前面的链表会被反复扫描。更高效的做法是使用优先队列最小堆。把所有链表的头节点放进堆里每次弹出最小的节点接在结果链表尾部然后把这个节点的下一个节点压入堆中循环直到堆为空。时间复杂度是 O(nk log k)空间复杂度 O(k)。这道题在面试里属于中高难度但它的基础正是 mergeTwoLists 的“两个链表比较值”这个简单动作。每学一个新题能主动往旧知识上靠技术体系才会慢慢织成网。4.3 两类题通用的思维模型回归数和合并链表它们有一个共同的思维模型分解并解决子问题。回归数把“判断一个数”分解成“取数字、算幂、累加”合并链表把“合并两个大链表”分解成“比较两个头节点 合并两个剩余链表”。一个偏数学一个偏指针底层的“递归分解”逻辑是一致的。我在带人的时候经常让他们刻意练习这种分解思维拿到一个没见过的题先别急着写代码出声说出“这个问题的子问题是什么”。能说清楚子问题代码基本就解决了一半。这个习惯比背题重要得多。5. 常见问题与排查技巧实录5.1 链表操作的经典翻车现场合并链表这题如果写错多半是下面几个原因。第一个是忘记更新 cur。很多初学者会写 cur.next l1 或 cur.next l2但忘记在每次赋值后执行 cur cur.next。结果就是链表只保留了最后一个节点前面的节点全丢了。我见过太多次这种写法调试半个小时才发现是少了这一行。第二个是修改了原链表的头节点。如果你在循环里直接拿 l1 当头节点操作后面返回的时候发现原链表结构已经被改得七零八落。正确的做法是用 dummy 节点兜底保留原链表的引用或者在遍历过程中用临时变量保存 next 节点。第三个是死循环。典型场景是循环条件写成了while l1 or l2但在循环体里没有对空链表做判断导致 l1 或 l2 之一为空时代码继续去访问l1.val或l1.next直接抛空指针异常。笔试环境可能直接报错面试现场就是自己调试半天找不出原因非常尴尬。解决这些问题的通用方法是“画图 走读”。随便拿两个短链表比如 [1,3,5] 和 [2,4]在纸上画出每一步执行后每个指针的位置。走完一遍代码里的问题基本自己就浮出来了。5.2 回归数的隐蔽 Bug回归数的代码很容易让人产生“我已经写对了”的错觉但有几个隐蔽 Bug 值得专门拿出来说。第一个是位数计算的位置问题。如果你的代码是边取数字边统计位数就会出错。比如 original153循环里每次 num 都变小你统计到的位数可能只有 3、2、1、0最后算出来的幂次全都是错乱的。必须在一开始就把 n 算好存起来。第二个是累加结果的变量类型。如果累加总和的变量用的是 int遇到大数字时可能溢出导致返回结果错误。在 Python 里没这问题但 C、Java、Go 都会遇到建议用 64 位整形。第三个是负数处理。有些同学直接套用循环负数取余在 Python 里结果还是正数但在 C 里结果可能是负数最终导致判断失败。稳妥的做法是开头就加一句if num 0: return False把负数直接排除。5.3 调试工具与方法建议链表类题目调试最直接的工具就是 print。可以在关键节点打印 val观察指针移动是否符合预期。如果用的是本地 IDE断点调试效果更好。回归数这类数学题调试的方式是“边界值测试”。分别测试 0、1、9、10、153、154、370、1634、9474 这些已知数据。把自己写的代码跑一遍结果和已知答案对不上就缩小数据范围继续测找到第一个出错的数然后单步跟踪。这个方法虽然土但效率极高。调试的时候可以多用“断言”而不是单纯 print。比如你可以写assert is_armstrong(153) is True跑一遍就知道所有用例是否通过比起肉眼盯着一堆 print 输出判断要靠谱得多。我平时刷题也一直是这样做的先把关键测试用例写成断言代码写完直接运行验证不用反复改代码去 add print。6. 写在最后一点个人体会回到开头说的那个观点回归数和合并链表其实都是“看似简单实则考察综合能力”的题目。回归数教会我如何把一个数学定义准确翻译成代码合并链表教会我如何在指针移动的细节里保持清醒。作为工程师这两项能力在真实项目里每天都在用。我个人在实际操作中有一个习惯每学一个算法题不急着刷下一个而是停下来问自己三个问题——这题考的是什么数据结构或数学原理我用了哪几种解法如果数据规模扩大 100 倍我的解法还行不行这个习惯帮我打下了挺扎实的基本功也让刷题不再是“过眼云烟”。如果你最近也在准备面试或者单纯想巩固基础花一个下午把这两个题的各种写法都吃透绝对值得。等你能不看答案把迭代和递归两个版本都默写出来再把边界条件讲得明明白白的时候你会发现自己写代码的底气都不一样了。
