力扣1290题二进制链表转整数详细教程
题目分析与解读
给你一个单链表的头节点head,链表中每个节点的值不是0就是1。已知这个链表表示一个无符号二进制数,请返回其对应的十进制整数。
难点解析:
链表表示的是一个二进制数,每个节点代表一位
链表头节点表示二进制数的最高位
需要将二进制转换为十进制
链表长度可能很长,需要考虑数值范围
现实生活场景类比
想象你在玩一个密码锁游戏,锁上有若干位数字,每位只能是0或1。你需要从左到右依次读取这些数字,把它们当作一个二进制数,然后计算出对应的十进制数字才能开锁。
比如密码锁显示:1→0→1
这是二进制数101
转换为十进制:1×4+0×2+1×1=5
所以密码是5
解题步骤详解
初始化结果变量?:sum=0
遍历链表?:从头节点开始,依次访问每个节点
二进制转十进制?:
对于每个节点值,将sum左移一位(相当于×2)
加上当前节点的值
4.返回结果?:遍历结束后sum即为十进制结果
注意事项
链表可能为空,但题目保证至少有一个节点
链表长度可能很长,结果可能超过int范围,所以使用longlong
二进制数的最高位是链表头节点
每次迭代都要先左移再相加,保证位权正确
不需要考虑负数情况,因为是无符号二进制数
代码实现与注释
classSolution{
public:
intgetDecimalValue(ListNode*head){
longlongsum=0;//初始化结果为0,使用longlong防止溢出
while(head){//遍历链表直到末尾
//将当前结果左移一位(相当于×2)并加上当前节点的值
sum=(longlong)sum*2+head-val;
head=head-next;//移动到下一个节点
}
returnsum;//返回十进制结果
}
};
总结分析?
这是一个链表操作和进制转换结合的问题:
链表操作:需要遍历链表获取每个节点的值
进制转换:二进制转十进制,每位权重是2的幂次
位运算:通过左移操作(×2)实现权重计算
这个问题的关键在于理解二进制数的表示方法和链表遍历技巧。代码通过简单的迭代和数学运算就完成了转换,时间复杂度O(n),空间复杂度O(1),体现了算法的高效性。