Easy

题目描述

给定一个单链表的头节点 head，链表中每个节点的值不是 0 就是 1。链表表示一个二进制数。

返回该链表所表示的二进制数的十进制值。

最高有效位在链表的头部。

示例 1：

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

示例 2：

输入：head = [0]
输出：0

约束条件：

  • 链表不为空
  • 节点数量不超过 30
  • 每个节点的值不是 0 就是 1

解题思路

这道题要求将二进制链表转换为十进制整数，有两种常见的解法：

方法一：字符串转换法 先遍历链表收集所有的二进制位，然后使用内置函数将二进制字符串转换为十进制。这种方法简单直观，但需要额外的存储空间。

方法二：位运算法（推荐） 这是更优雅的解法，利用二进制转十进制的数学原理：每遇到一个新的位，就将当前结果左移一位（相当于乘以2），然后加上新位的值。

具体过程：

  • 初始化结果为 0
  • 遍历链表，对于每个节点：
    • 将当前结果左移一位（result << 1 或 result * 2）
    • 加上当前节点的值

这种方法的优势是只需要 O(1) 的额外空间，且效率更高。以 [1,0,1] 为例：

  • 初始：result = 0
  • 处理 1：result = (0 « 1) + 1 = 1
  • 处理 0：result = (1 « 1) + 0 = 2
  • 处理 1：result = (2 « 1) + 1 = 5

代码实现

class Solution {
public:
    int getDecimalValue(ListNode* head) {
        int result = 0;
        while (head != nullptr) {
            result = (result << 1) + head->val;
            head = head->next;
        }
        return result;
    }
};

class Solution:
    def getDecimalValue(self, head: Optional[ListNode]) -> int:
        result = 0
        while head:
            result = (result << 1) + head.val
            head = head.next
        return result

public class Solution {
    public int GetDecimalValue(ListNode head) {
        int result = 0;
        while (head != null) {
            result = (result << 1) + head.val;
            head = head.next;
        }
        return result;
    }
}

var getDecimalValue = function(head) {
    let result = 0;
    while (head !== null) {
        result = (result << 1) + head.val;
        head = head.next;
    }
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度数值
时间复杂度O(n)
空间复杂度O(1)

其中 n 是链表的长度。我们需要遍历整个链表一次，每个节点的处理时间为常数时间，因此时间复杂度为 O(n)。我们只使用了常数个额外变量，空间复杂度为 O(1)。