1290. 二进制链表转整数
题目描述
输入单链表的头节点 head，链表用数组表示，例如 [1,0,1]。每个节点的值是 0 或 1。
从头到尾读出这些值，就是一个二进制数，链表开头是最高位。返回这个二进制数对应的十进制整数。
示例 1
输入：head = [1,0,1] 输出：5
解释：二进制 101 等于十进制 5。
示例 2
输入：head = [0] 输出：0
数据范围
- 链表非空。
- 节点总数不超过 30。
- 每个节点的值是
0或1。
解题思路
我们事先不知道链表长度，没法直接算每一位的权重。换个思路：从高位往低位读，维护 ans = 已读入的那些位组成的二进制数。每读入一位 bit，就令 ans = ans * 2 + bit，相当于把已有结果左移一位，再把 bit 放到最低位。
为什么正确
读完前 k 个节点后，ans 等于这 k 位组成的二进制数的值。
复杂度分析
时间 O(n)，额外空间 O(1)。
易错点
不要写成 ans * 10 + bit，那是十进制拼接。也不必先求长度再按 2 的幂累加，一次遍历就够了。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def getDecimalValue(self, head: Optional[ListNode]) -> int:
ans = 0
while head:
ans = ans * 2 + head.val
head = head.next
return ansclass Solution {
public int getDecimalValue(ListNode head) {
int ans = 0;
while (head != null) {
ans = ans * 2 + head.val;
head = head.next;
}
return ans;
}
}class Solution {
public:
int getDecimalValue(ListNode* head) {
int ans = 0;
while (head) {
ans = ans * 2 + head->val;
head = head->next;
}
return ans;
}
};func getDecimalValue(head *ListNode) int {
ans := 0
for head != nil {
ans = ans*2 + head.Val
head = head.Next
}
return ans
}var getDecimalValue = function(head) {
let ans = 0;
while (head) {
ans = ans * 2 + head.val;
head = head.next;
}
return ans;
};function getDecimalValue(head: ListNode | null): number {
let ans = 0;
while (head) {
ans = ans * 2 + head.val;
head = head.next;
}
return ans;
}