力扣1290.二进制链表转整数

题目本质

给定一个单链表的头节点head，链表中每个节点的值为0或1。链表表示一个‌最高有效位在前‌的二进制数字，要求将其转换为对应的十进制整数。例如链表1→0→1对应的二进制数是101，应返回十进制数5。

解题思路与推导过程

一、算法核心思想

1. ‌1.二进制数构造规则‌：

• 每个新节点的值相当于二进制数‌向左移位‌后的最低位

• 例如遍历到第三个节点时，计算过程相当于(前值<<1) | 当前值

2. ‌2.累加计算‌：

• 初始化sum=0作为累加结果

• 每次循环执行sum = sum*2 + 当前节点值（等价于位运算sum<<1 | val）

3. 3‌.遍历特性‌：

• 无需反转链表，直接按照遍历顺序处理

• 时间复杂度O(n)，空间复杂度O(1)

二、代码流程解析

• ‌1.初始化‌：sum=0作为十进制结果的容器

• ‌2.循环处理每个节点‌：

1. sum = sum*2：将之前的结果左移一位（二进制进位）

2. +head->val：将当前位的二进制值加入最低位

3. head=head->next：指针后移处理下一位

• 3‌.终止条件‌：链表指针指向NULL时结束遍历

三、潜在问题与解决方案

• ‌大数溢出‌：使用long long类型存储中间结果（题目保证链表长度≤30，long long足够存储2^30量级的数值）

• ‌头节点为空的边界情况‌：题目约束链表非空，无需额外判断1

代码+注释

class Solution {
public:
    int getDecimalValue(ListNode* head) {
        long long sum=0; // 使用long long避免中间计算溢出
        while(head)      // 遍历直到链表末尾
        {
            // 核心计算公式：每次将之前结果左移一位，并加上当前二进制位
            sum = (long long)sum*2 + head->val; 
            
            // 类型转换说明：防止sum超过int范围时的计算错误
            head = head->next; // 指针后移处理下个节点
        }
        return sum; // 最终结果自动转为int（题目保证数值在int范围内）
    }
};