二进制链表转整数：一次遍历与位运算的精妙结合

LeetCode 1290这道题我在刷LeetCode热门100题的时候顺手点进去做过一遍题面很短解法也不复杂但后来回看才发现它把两个高频考点——链表遍历和二进制按位转换——压在了同一道题里。标题里耗时100应该是指当时那次提交的耗时数据这篇文章我就围绕这道二进制链表转整数题目把解法、位运算原理、性能复盘以及延伸变体一次讲透。适合刚开始刷链表题的人也适合想巩固位运算和进制转换手感的老手。1. 题目拿到手先别急着写循环1.1 题目到底在说什么原题描述一句话给你一个单链表的头节点 head链表每个节点存储一位二进制数只会是 0 或 1并且链表头是二进制数的最高位依次往后走到尾节点是最低位要求返回这个二进制数对应的十进制整数值。比如例子输入head [1,0,1]输出5解释1 * 2^2 0 * 2^1 1 * 2^0 5。输入head [0]输出0。输入head [1]输出1。题目给了几个例子其中单节点链表这个例子很关键它提醒你别忘记只有一个节点的情况。这种题在 LeetCode 上被标为 Easy但 Easy 不等于没细节很多人在简单题上翻车翻的往往不是算法而是边界。我刷题的时候会把这种题归类到链表基本功题库里它不考复杂的指针操作也不考动态规划考点非常纯粹你能否把二进制权重和链表遍历顺序对应起来。1.2 最容易误解的点头节点是最高位我第一次做这道题时脑子里第一反应是从尾节点往头节点走依次乘以 1、2、4、8……结果发现单链表压根没法往回走。这就是这道题最核心的细节链表的遍历方向是从最高位到最低位而我们计算时希望先拿到最低位这样权重可以直接从 1 开始累加。这个方向不一致是整道题最容易踩的坑。如果你没有意识到这个问题很容易写出下面这种半吊子代码先遍历一遍把链表长度数出来再遍历第二遍计算 power 2^(len-1-i)。这种写法能过但它暴露了一个问题你没有利用边遍历边累积的思路。换个角度想与其先知道全貌再计算不如每走一步都让已经读到的部分变得更大。这两种思路前者是数组思维后者才是链表题该有的手感。链表题最怕的就是把链表转成数组然后按数组下标去计算这种解法虽然 AC 没问题但完全失去了训练的意义面试的时候面试官大概率会让你现场写一遍不用额外空间的版本。1.3 边界条件少看一眼就提交这道题的边界条件不多但很重要链表可能只有一个节点值为 0 或 1。节点值只可能是 0 或 1不会出现负数也不需要校验非法输入。题目一般保证 head 非空但你自己写测试时仍应覆盖空链表的情况防御性编程总是好的。我在本地自测时会写一个 build_linked_list 辅助函数把数组转成链表然后再跑目标函数输出结果。LeetCode 上你只需要填充函数体但平时训练建议把测试环境搭完整这样调试起来更快。边界条件这种细节多花 30 秒能省下一次 WA 的折腾。2. 两种实现路线建议直接练第二种2.1 路线一先转数组再按位累加最容易想到的做法分两步第一次遍历把链表的值存进一个普通数组第二次遍历数组通过下标计算每一位的权重def getDecimalValue(head: ListNode) - int: values [] while head: values.append(head.val) head head.next ans 0 n len(values) for i, val in enumerate(values): ans val (n - 1 - i) return ans时间 O(n)空间 O(n)。这段代码非常直观适合刚接触链表的人理解题目含义也适合笔试时间紧张时快速 AC。但它的缺点也明显明明只需要 O(1) 的额外空间就能完成的事你多申请了一个数组。还有一种更省事的 Python 写法遍历链表的同时把 val 转成字符串存起来最后 int(.join(bits), 2) 一把梭。这个在 Python 里确实能跑但我强烈不建议在面试或者实际项目里用它把核心逻辑完全藏进了内置函数面试官想考察的链表操作一点都没体现。写出来可能还得被追问一句还有别的方法吗到时候现想反而更慌。2.2 路线二一次遍历的按位累加正确的、也是官方推荐的做法是一个极其简洁的循环def getDecimalValue(head: ListNode) - int: ans 0 while head: ans ans * 2 head.val head head.next return ans不到十行。核心思想是每次读到新的一位就把之前的结果整体左移一位二进制意义下再加上当前位。这个操作也可以写成位运算版本ans (ans 1) | head.val两种写法等价ans * 2和ans 1结果完全一样 head.val和| head.val在这里也完全一样因为 head.val 只能是 0 或 1且当前最低位一定是空的。我建议你在草稿纸上把十进制里乘以 10 加数字和二进制里乘以 2 加数字类比一下这个套路记住之后好多题都能用。2.3 两条路线对比为什么我更推荐第二种我整理了一张表方便你对照对比维度路线一数组辅助路线二边遍历边累积时间复杂度O(n)O(n)额外空间O(n)O(1)代码量约 10 行约 6 行主要出错点数组下标容易写错容易忘记乘 2对链表训练的价值低本质是数组题高练的是状态累积你可能会说空间 O(n) 和 O(1) 在这道题里差别不大反正链表最长才 30 位。这话没毛病但我要提醒你LeetCode 1290 的链表节点数限制是 1 到 30因为二进制位超过 30 的话32 位 int 可能溢出所以题目特意做了限制。但这道题训练的是思维习惯如果你习惯了先转数组再算遇到后面 445 题两数相加 II这种链表题你会发现数组化有时候反而不方便。反过来如果你习惯了一手遍历一手累积很多中等难度的链表题会顺很多。3. 位运算原理为什么 ans ans * 2 val 能成立3.1 先用十进制的例子理解累积我每次讲这道题都会先让朋友回忆一个小学就学过的操作给定字符串 123怎么转成整数 123你可能会写 int(123)但如果你手写实现一定是这样num 0 for ch in 123: num num * 10 int(ch)过程是0 - 1 - 1*10212 - 12*103123。每读到一个新数字旧结果整体扩大十倍然后加上新数字。二进制链表转整数完全同理只是把扩大十倍换成扩大两倍读入第一位 10*21 1此时表示二进制 1对应十进制 1。读入第二位 01*20 2表示二进制 10对应十进制 2。读入第三位 12*21 5表示二进制 101对应十进制 5。这个乘以基数再加新位的模式是所有进制转换的核心。十进制的基数是 10二进制的基数是 2八进制就是乘以 8十六进制就是乘以 16。理解了这一层你以后再遇到字符串转整数罗马数字转整数Excel 列号转数字这些题会发现它们本质是同一道题。LeetCode 上这类题不少名字各不相同但底层的累积逻辑一模一样。3.2 为什么可以用位运算版本以及一个优先级大坑ans ans * 2 head.val写成位运算ans (ans 1) | head.val原因是左移一位在二进制层面就是整体乘以 2而最低位原来是 0按位或上一个 0 或 1 正好等价于加法。之所以用按位或而不是加法是因为位运算语义上更贴近拼接二进制位这个动作读代码的人一眼能看出你在处理二进制位而不是普通乘法。这里有一个超级容易踩的坑ans 1 head.val千万不要这么写。因为 Python 里加法优先级高于移位这行代码实际是ans (1 head.val)也就是左移 1 或 2 位结果完全不对。类似的坑在 C/C 里也存在的优先级低于加法。如果你不确定优先级就老老实实加括号或者干脆用乘法版本。我见过好几个朋友在周赛时被这种优先级小坑浪费了好几分钟真的没必要。为了验证这个坑你可以在本地 Python 环境里跑一下ans 1 val 1 print(ans 1 val) # 结果是 8因为实际是 ans (11) 1 2 4等等112124诶这里我故意写了一个容易让人困惑的案例。实测算一下1 val当 val1 时等于 21 2等于 4而正确结果应该是(1 1) | 1 3。这个差异非常隐蔽尤其是当 ans 比较小的时候你很难一眼看出结果错在哪。所以我的建议是位运算一律加括号不要跟优先级赌运气。3.3 溢出问题题目限制的巧妙之处你可能会好奇为什么这道题的链表长度限制是 30而不是 100 或者 1000因为 2^30 约等于 10.7 亿如果链表长度到 31二进制最高位是 1 时结果就可能超过 32 位有符号整数的上限 21.4 亿。LeetCode 把范围故意限定在 30 以内就是为了让所有语言都能用 int 安全通过。但如果你自己在扩展问题里做任意长度二进制链表转整数就要考虑大数处理了。Python 里 int 无限大随便算Java 里可以用 BigInteger或者干脆用字符串表示结果C 里可以用数组模拟大数。我在实际刷题中更推荐的做法是先问清楚题目的数据范围再决定用 int 还是上大数方案不要一上来就写一堆无用的防御代码。数据范围意识是这个阶段最值得培养的很多 Medium 题你写对了思路但溢出翻车就是栽在这里。4. 耗时 100ms 的复盘性能到底由什么决定4.1 一次真实提交记录标题里写的耗时100可能就是我当时提交时 LeetCode 显示的一次运行耗时大约 100ms 左右。这种数字在 LeetCode 上看过几千次之后我的结论是它参考价值有限。原因很简单LeetCode 的耗时是后台评测机跑出来的跟当时的机器负载、同一时间提交的人数、甚至语言版本都有关系。同一份代码早提交和晚提交可能从 80ms 波动到 120ms完全没有规律。这道题用 Python 提交100ms 这个量级对 Python 来说很正常。链表节点最多 30 个循环体里就一个乘法和加法理论上微秒级就能算完。之所以显示 100ms主要是 LeetCode 的 Python 接口每次提交会包含测试用例调度、函数调用、结果校验等固定开销真正执行你算法的时间极其短。你要是把这段代码放到本地空跑时间复杂度根本看不出任何性能压力。4.2 真正影响性能的往往不在算法本身如果你仔细看这道题的 LeetCode 讨论区会发现有人贴出 0ms 的 C 语言解法也有人贴出 60ms、100ms 的 Python 解法于是有人得出结论Python 就是比 C 慢。这话部分正确但对于这个数据规模来说语言差异根本不重要。算法复杂度从 O(2^n) 优化到 O(n)是数量级的提升而把ans ans * 2 head.val改成ans (ans 1) | head.val只是常数级别的优化。在 Python 里真正影响这道题耗时的反而是循环里访问属性的方式。比如while head: ans (ans 1) | head.val head head.next每次循环都要对head.val做一次属性查找。如果追求极致可以把 val 先存成局部变量但说实话对 30 个节点的链表毫无必要。我的观点是在 LeetCode 这个平台上与其纠结几毫秒的差异不如把代码写清楚、把复杂度算对、把边界测全这三点对面试和实际工作的价值远大于击败 99% 的用户。4.3 一道题的快应该定义在算法复杂度上我最开始刷题的时候也喜欢刷击败百分比后来发现这个数字误导性很强。性能优化的正确顺序永远是选择正确复杂度的算法再优化常数最后才考虑语言底层的微优化。1290 这道题线性扫描一次已经是最优复杂度因为你至少要把每个节点的值读一遍才能算出结果不可能有低于 O(n) 的解法。所以当你看到别人提交 100ms、自己提交 70ms 时不用太兴奋看到别人 150ms、自己 50ms 时也不用太得意。真正值得关注的是你的解法是否做到了 O(n) 时间、O(1) 空间边界情况是否都处理了代码是否能让三个月后的自己一眼看懂这三点才是衡量一道题是否真正掌握的标准。5. 从 1290 延伸出去三个值得练的变体5.1 变体一链表表示的是低位到高位如果把题目改一下链表头是最低位尾节点是最高位比如 [1,0,1] 表示最低位是 1、第二位是 0、最高位是 1即二进制 101 反过来对应十进制 3。这种题也经常出现直观做法有两种方案一先把链表反转变成最高位在头再用 1290 的逻辑计算。反转链表刚好是 LeetCode 206 题两者组合起来就是一道不错的面试题。方案二不反转一边遍历一边用位权累加每走一个节点权重翻倍def get_decimal_from_lsb(head: ListNode) - int: ans, weight 0, 1 while head: if head.val 1: ans weight weight 1 head head.next return ans我个人更推荐方案一因为反转链表本身就是一个考点而且反转后的代码更贴近原题面试时沟通成本低。方案二虽然也能过但它和低位到高位的权重逻辑耦合得更紧面试时一旦被问到为什么 weight 每次都左移一位你还需要额外解释一遍反而不如反转方案直白。5.2 变体二整数转二进制链表正好是反向操作从十进制整数构造一个二进制链表输入 5输出 [1,0,1]。这个反向操作也很常见核心是不断取模和整除def int_to_binary_linked_list(num: int) - ListNode: if num 0: return ListNode(0) bits [] while num: bits.append(num % 2) num // 2 bits.reverse() dummy ListNode() cur dummy for bit in bits: cur.next ListNode(bit) cur cur.next return dummy.next注意num 0的特判否则你会返回一个空链表或者漏掉最低位。这种正向转反向、反向再转正向的训练能帮你把进制转换和链表遍历彻底锁在一起。我练这个变体的时候会特意用 0、1、5、8、255 这几个数各跑一遍确保特判和反转逻辑都没问题。5.3 变体三两个二进制链表相加进位处理LeetCode 445 题两数相加 II虽然不是二进制而是十进制但思路可以直接迁移最高位在链表头做加法时需要从最低位开始所以可以先反转两条链表逐位相加并维护进位 carry最后把结果链表再反转回来。二进制版本同理只是逢二进一。这个变体最能检验你是否真懂了 1290。因为翻转、遍历、进位、结果重建四步缺一不可。如果 1290 你只背了ans ans * 2 val而没有理解每一位的权重关系遇到两数相加大概率会在到底先反转谁上卡壳。反过来如果你能独立写出二进制链表相加的完整代码二进制链表的题目基本就通关了。建议你动手写一版不要看一眼答案觉得哦我会了就关掉真的写出来才知道哪里会断。6. 这道简单题给我的三点教训6.1 陷阱常藏在方向和边界里做了几百道题之后回头看1290 的难点不在算法而在方向感。链表头是最高位遍历方向是从高到低这和很多人本能的从低到高按权重累加相反。一旦方向想清楚解法几乎是水到渠成。这也是我自己的一个习惯拿到链表题先在草稿纸上画出节点的顺序、标明哪边是高位哪边是低位再动手写代码。这一步看似浪费时间实际能避免大部分返工。特别是参加周赛的时候时间紧张画图反而能让你第一时间发现题目里的顺序陷阱。6.2 简单题是进阶题的地基别因为它 Easy 就跳过LeetCode 热门 100 题里有很多简单题1290 虽然不在 Top 100 里但同类的基础题值得反复刷。我见过不少人刷题专挑 Medium 和 Hard觉得简单题没营养结果面试时被一道反转链表问得卡壳。基础题的价值在于把手感和原理练透让你在做中等题时不用再花精力想基础步骤。1290 用到的是链表遍历和进制转换这两个最基本的能力这两样不牢后面 445、2 这两道加法题都会很吃力。6.3 最后一个关于刷题节奏的小建议我现在的做法是简单题每天挑两三道练手感重点在速度和准确率中等题每天一道到两道重点在思路完整度和代码清晰度难题一周一两道重点是学习新套路。1290 这种题我会要求自己 2 分钟内写完然后马上做它的变体。这样既不会在简单题上消耗太多时间也不会因为轻视基础题而丢掉基本功。如果你也打算按这个节奏刷建议把你做过的每道简单题变体都记到笔记里时间久了你会发现很多所谓的新题不过是旧知识点的重新组合。