LeetCode 1290. 二进制链表转整数

2025-07-18 HGNULB 约 7 分钟

文章信息 7 个分类 2 个标签

分类

题目描述

✅ 1290. 二进制链表转整数

题意分析

链表的每个节点只存 0 或 1，从头节点到尾节点依次读出来就是一个二进制数的高位到低位，要求返回它对应的十进制值。

「高位在前」这个方向非常重要。如果低位在前，就得先知道链表有多长才能确定每一位的权重；而高位在前意味着可以边走边算，无需回头。这也解释了为什么本题被定为简单题——数据的排列方向恰好和累积计算的方向一致。

约束里写明节点数不超过 30、每个 val 只可能是 0 或 1，所以结果最大是 $2^{30} - 1$，稳稳落在 32 位有符号整数范围内，不需要担心溢出，也不需要用 long。看到这个上界就可以放心用 int 累加。

单链表只能从头往后走、拿不到长度也拿不到前驱，因此任何需要「先知道总位数再算权重」的方案都要额外跑一趟或者额外开空间。

边界上，题目保证链表至少有一个节点，所以不存在空链表；但值得注意 head 可能就是单个 0，此时答案是 0，任何做了「跳过前导零」之类特殊处理的写法都要保证这个用例仍然返回 0。

解法：遍历累积

核心思路

最自然的想法是先把所有位收集到数组里、记下长度 n，再用 $\sum b_i \cdot 2^{n-1-i}$ 求和。它能算对，但要遍历两趟（或者一趟遍历加一次额外存储），并且需要维护一个不断变化的权重 $2^{n-1-i}$，写起来啰嗦。

瓶颈在于「权重依赖于总长度」。而观察到一个事实可以彻底绕开它：在二进制里，把已经读到的数整体左移一位（乘 2），再把新读到的位加到末尾，就等于在原数右侧追加一个二进制位。这正是霍纳法则在基数 2 下的形式。

于是维护一个累加器 res，循环不变量是：每处理完一个节点，res 恰好等于「从头节点到当前节点」这段前缀所表示的二进制数的十进制值。初始时前缀为空，空串的值定义为 0，所以 res = 0 正确；每读一个节点执行 res = res * 2 + cur.val，前缀增长一位，不变量得以维持；走到链表尽头时，前缀就是整条链表，res 就是答案。

这个写法的好处是全程不需要知道链表长度、不需要任何额外存储、只遍历一趟，是面试官期待的标准答案。它和「字符串转整数」用的其实是同一个骨架，只是基数从 10 换成了 2。

解题步骤

初始化 res = 0：它代表「已读前缀的值」，而空前缀的值就是 0。这个初值同时天然处理了链表首位为 0 的情况——乘 2 加 0 仍是 0，前导零不会产生任何影响，所以不需要单独跳过前导零。

用 cur 从 head 开始遍历，条件写 cur != null：用 cur 而不是 cur.next 作条件，才能保证最后一个节点也被计入；用 cur != null 也让「只有一个节点」的链表自然走完一轮。

每轮执行 res = res * 2 + cur.val：res * 2 把已有的位整体左移一位腾出最低位，+ cur.val 把新的一位填进去。这两步的顺序不能交换——先加后乘会把新位也一起左移，权重整体错一位。

推进 cur = cur.next：本题不修改任何指针，所以不需要像反转链表那样先暂存后继。

返回 res：循环退出时 cur 为空，已读前缀就是整条链表。

以 1 → 0 → 1 → 1 走一遍（十进制应为 11）。

初始：res = 0，cur 指向首个节点 1。

第一轮：res = 0 * 2 + 1 = 1，前缀是 1，值 1，正确；cur 移到 0。

第二轮：res = 1 * 2 + 0 = 2，前缀是 10，值 2，正确；cur 移到第三个节点 1。

第三轮：res = 2 * 2 + 1 = 5，前缀是 101，值 5，正确；cur 移到第四个节点 1。

第四轮：res = 5 * 2 + 1 = 11，前缀是 1011，值 11，正确；cur 变成 null。

循环退出，返回 11。可以看到每一轮结束时 res 都精确等于当前前缀的值，不变量始终成立。

再看首位为 0 的用例 0 → 1：第一轮 res = 0 * 2 + 0 = 0，第二轮 res = 0 * 2 + 1 = 1，返回 1，前导零被 res = 0 的初值自动吸收，无需特判。

代码实现

class Solution {
    // 每次 res = res \ 2 + node.val。
    public int getDecimalValue(ListNode head) {
        int res = 0;
        ListNode cur = head;
        while (cur != null) {
            res = res * 2 + cur.val;
            cur = cur.next;
        }
        return res;
    }
}

func getDecimalValue(head *ListNode) int {
    // 每次 res = res \ 2 + node.val。
    res := 0
    cur := head
    for cur != nil {
        res = res*2 + cur.Val
        cur = cur.Next
    }
    return res
}

复杂度分析

时间复杂度：$O(n)$，其中 $n$ 是链表节点数。只走一趟，每个节点做一次乘法、一次加法和一次指针推进，全是常数操作。

空间复杂度：$O(1)$，只用了 res 和 cur 两个变量，与链表长度无关。不需要把节点值先存进数组，这是本解法相对「先收集再加权」写法的核心优势。

关键点总结

高位在前的数位序列，用 res = res * base + digit 一趟累积即可，无需知道总位数；把基数换成 10 就是字符串转整数，换成 16 就是十六进制解析，这个骨架完全通用。

循环不变量「res 等于已读前缀的值」是这段代码的灵魂，面试时主动说出来，比逐行读代码更能体现理解深度。

累加器初值 0 同时承担了「空前缀」和「吸收前导零」两个职责，因此不需要任何特判分支——能省掉特判往往是状态定义选对了的信号。

先看数据范围再决定用什么类型：本题上界 $2^{30}-1$ 明确落在 int 内，可以直接说「不会溢出」；如果节点数放宽到 64，同样的代码就必须换 long 或改用大数。

单链表只能单向遍历，凡是「权重依赖总长度」的思路都要多一趟或多一份空间，优先寻找与遍历方向一致的递推式，这是链表题的通用取舍。

易错点总结

写成 res = res + cur.val * 2：1 → 0 → 1 → 1 会得到 1+0+2+2=5，把「左移已有结果」错当成「放大新位」，权重完全错乱。

顺序写反成 res = (res + cur.val) * 2：同样的输入会得到 22，整体多乘了一个 2，最低位的权重变成 2 而不是 1。

误以为链表是低位在前，用 res += cur.val << i 且 i 递增：1 → 0 会返回 1 而不是 2，恰好在回文串如 1 → 0 → 1 上又能得到正确答案，很难被弱用例发现。

循环条件写成 cur.next != null：最后一个节点不参与累积，1 → 0 → 1 → 1 只算到 101 返回 5，结果永远是正确值除以 2 再向下取整。

res 初值写成 head.val 却仍从 head 开始遍历：首位被重复计入，1 → 1 会得到 (1*2+1)*2+1 = 7 而不是 3。

额外写「跳过前导零」的逻辑：链表就是单个节点 0 时，跳过后 cur 直接变成 null，返回值可能变成未初始化的默认值或抛空指针，而正确答案是 0。

为了求权重先遍历一遍求长度，却在第二趟复用了同一个已经走到尾的 cur：第二趟一次循环都不进，直接返回 0，这是两趟写法最常见的翻车点。

用 Integer.parseInt(sb.toString(), 2) 拼串后交差：这把考点（数位累积）整个绕开了，面试中会被要求重写；而且拼接字符串带来 $O(n)$ 额外空间，反而更差。

担心溢出而给 res 加取模：题目上界只有 $2^{30}-1$，取模会让 1 后面跟 30 个 1 这类最大用例返回错误的余数。

相似题目

题目	难度	考察点
8. 字符串转换整数 (atoi)	中等	同样是逐位累积，但基数为 10 且必须处理符号、空格与溢出截断
7. 整数反转	中等	反向拆位再累积，重点在溢出前的预判而非遍历本身
67. 二进制求和	简单	二进制但要求逐位进位模拟，因为串长可能远超整数表示范围
191. 位1的个数	简单	反过来把整数拆成二进制位，用 `n & (n-1)` 逐个消去最低位的 1
2. 两数相加	中等	链表低位在前，只能边走边进位，不能先转成整数再相加
445. 两数相加 II	中等	与本题一样高位在前，但结果超出整数范围，必须借栈从低位开始计算
206. 反转链表	简单	若坚持从低位开始算，需要先反转链表，是本题的一个备选前置步骤
234. 回文链表	简单	同样是一趟遍历难以直接比对，需要快慢指针配合反转后半段
剑指 Offer 06. 从尾到头打印链表	简单	输出顺序与遍历方向相反，只能靠栈或反转来调头