线性遍历+二进制 6行代码征服二进制链表转整数
3个月前 (05-17)
力扣1290.二进制链表转整数
题目本质
给定一个单链表的头节点head，链表中每个节点的值为0或1。链表表示一个最高有效位在前的二进制数字，要求将其转换为对应的十进制整数。例如链表1→0→1对应的二进制数是101，应返回十进制数5。
解题思路与推导过程
一、算法核心思想
1.二进制数构造规则：
每个新节点的值相当于二进制数向左移位后的最低位
例如遍历到第三个节点时，计算过程相当于
(前值<<1) | 当前值2.累加计算：
初始化
sum=0作为累加结果每次循环执行
sum = sum*2 + 当前节点值（等价于位运算sum<<1 | val）3.遍历特性：
无需反转链表，直接按照遍历顺序处理
时间复杂度O(n)，空间复杂度O(1)
二、代码流程解析
1.初始化：
sum=0作为十进制结果的容器2.循环处理每个节点：
sum = sum*2：将之前的结果左移一位（二进制进位）+head->val：将当前位的二进制值加入最低位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范围内）
}
};原创内容 转载请注明出处
