1290. 二进制链表转整数 Easy

给你一个单链表的引用结点 head。链表中每个结点的值不是 0 就是 1。已知此链表是一个整数数字的二进制表示形式。

请你返回该链表所表示数字的十进制值 。

示例 1:
输入：head = [1,0,1]
输出：5
解释：二进制数 (101) 转化为十进制数 (5)

示例 2:
输入：head = [0]
输出：0

示例 3:
输入：head = [1]
输出：1

示例 4:
输入：head = [1,0,0,1,0,0,1,1,1,0,0,0,0,0,0]
输出：18880

示例 5:
输入：head = [0,0]
输出：0

解题思路

输入： 一个代表二进制数的链表 head，每个节点的值为 0 或 1

输出： 返回链表表示的二进制数对应的十进制整数

本题属于链表遍历类问题。我们需要从左到右依次读取每个节点的值，并按二进制的规则将其转换为十进制。

方法一：位运算构造整数（推荐）

• 使用一个变量 result 记录当前结果。每遍历一个节点，将 result 左移一位（即 result << 1，相当于乘以 2），再加上当前节点的值（即 curr.val）。
• 完整操作为：result = (result << 1) | curr.val。
• 当遍历完成后，result 即为最终的十进制值。

该方法无需额外空间，时间复杂度为 O(n)，空间复杂度为 O(1)。

方法二：拼接字符串再转十进制

也可以在遍历过程中将每个节点的值拼接成一个二进制字符串 s，遍历结束后使用 int(s, 2) 将其转换为十进制。

此方法思路直观，但涉及字符串拼接，效率略低于方法一。

代码实现

python

class Solution:
    def getDecimalValue(self, head: Optional[ListNode]) -> int:
        result = 0  # 初始化结果为0
        curr = head

        # 遍历链表，将二进制逐位左移并加上当前位的值
        while curr:
            # 左移一位，相当于乘2，然后加上当前位
            result = (result << 1) | curr.val  
            curr = curr.next
        
        return result

javascript

const getDecimalValue = function(head) {
    let curr = head;
    let result = 0; // 初始化结果为0

    // 遍历链表，将二进制逐位左移并加上当前位的值
    while (curr != null) {
        // 左移一位，相当于乘2，然后加上当前位
        result = (result << 1) | curr.val; 
        curr = curr.next;
    }
    
    return result;
};

复杂度分析

时间复杂度：O(n)

空间复杂度：O(1)

链接

1290 国际版

1290 中文版