LeetCode 1290. 二进制链表转整数

约 3 分钟
文章信息 7 个分类 2 个标签
分类
LeetCode CodeTop 简单 未解决 2-5 阿里 百度
标签
数学 链表

题目描述

✅ 1290. 二进制链表转整数

image-20260928223925246

image-20260928223925247

题意分析

链表的每个节点保存一个二进制位，最高位在头部，要求返回整条链表表示的整数。输入非空且最多有 $30$ 位，最大值是 $2^{30}-1$，代码使用的整数类型可以容纳。

解法：遍历累积

核心思路

[!blue]

从高位到低位读数时，可以不断把新位接到已经读取的二进制前缀末尾。假设旧前缀的数值是 res，追加一位后，旧前缀的每一位都向高位移动一格，位权全部乘二；新节点值则占据最低位。因此更新规则是 res = res * 2 + cur.val。

用 res = 0 表示还没有读取任何位，cur 指向下一个要读取的节点。每轮更新后，res 恰好等于从头节点到当前节点这个前缀的值，再令 cur 指向后继。这个不变量一直保持，到 cur 为空时，整个链表都已读完，res 就是答案。

这种累积方式由新位推动已有位权变化，无需提前计算链表长度或单独求每一位的幂。前导零只会使前缀暂时保持为 $0$，不需要特判；遍历仅移动局部指针，不修改任何节点的连接。

解题步骤

  1. 初始化 res = 0、cur = head。
  2. 当 cur 非空时，执行 res = res * 2 + cur.val，把当前位加入前缀。
  3. 令 cur = cur.next，继续处理下一位。
  4. 遍历结束后返回 res。

代码实现

class Solution {

    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 := 0
    cur := head
    for cur != nil {
        // 已有二进制前缀左移一位，再加入当前位。
        res = res*2 + cur.Val
        cur = cur.Next
    }
    return res
}

复杂度分析

  • 时间复杂度：$O(n)$，每个节点访问一次。
  • 空间复杂度：$O(1)$，只保存前缀值和当前指针。

关键点总结

[!green]

  • 已有前缀乘二，新位按个位加入。
  • 循环检查当前节点，保证末尾节点也被处理。

易错点总结

[!yellow]

  • 先加新位再整体乘二，会让结果多乘二。
  • 把新位乘二而不移动旧前缀，会丢掉位置权重。
  • 把方向当成低位在前，会在非回文位串上得到错误结果。

相似题目

题目 难度 关联与区别
1022. 从根到叶的二进制数之和 简单 同样沿结构按乘2再加当前位累积二进制值，本题只有一条链，原题要累加多条根到叶结果。
171. Excel 表列序号 简单 同样按位权累乘累加，Excel列名使用无零数码的26进制，本题使用普通二进制。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2025/92674116
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！