基本信息
文件名称:力扣1290题(二进制链表转整数)详细教程.docx
文件大小:14.04 KB
总页数:3 页
更新时间:2025-06-01
总字数:约1.06千字
文档摘要

力扣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),体现了算法的高效性。