力扣每日一题--2025.7.14-EW帮帮网

📚 力扣每日一题–2025.7.14

📚 1290. 二进制链表转整数（简单）

今天我们要解决的是力扣上的第 1290 题——二进制链表转整数。

📝 题目描述

在这里插入图片描述

🤔 思路分析

我们知道二进制转十进制的公式是：Σ(bit_i × 2^(n-1-i))。

bit_i ：二进制数第i位的值（0或1），i从0开始计数（从左向右数）
n ：二进制数的总位数
2^(n-1-i) ：当前位的权重（2的幂次）

基于这个公式，我们可以通过两种视角来解决问题：

核心思路：

无论采用哪种方法，核心都是要处理以下两个关键点：

确定每个二进制位的权重（2的幂次）
累加各个位的值与其权重的乘积

📑 代码实现：

方法一：直接遍历链表（数学累加法）

public class Solution {
    public int getDecimalValue(ListNode head) {
        int decimalValue = 0;
  
        // 遍历链表时，每个节点代表更高一位的二进制值
        // 例如链表 1->0->1 的处理过程：
        // 第1次：0*2 +1=1   (二进制: 1)
        // 第2次：1*2 +0=2  (二进制: 10)
        // 第3次：2*2 +1=5  (二进制: 101)
        while (head != null) {
            decimalValue = decimalValue * 2 + head.val; // 等效于左移后叠加
            head = head.next;
        }
  
        return decimalValue;
    }
}

📊 方法二：使用位运算（优化空间版）

我们也可以使用位运算来实现这个转换，这样代码会更加简洁。

public class Solution {
    public int getDecimalValue(ListNode head) {
        int decimalValue = 0;
  
        // 位运算的优势：
        // 1. 避免乘法运算，提升计算效率
        // 2. 更直观体现二进制操作本质
        // 例如：假设当前累计值是101（二进制），左移后变成1010，与当前位或运算即完成叠加
        while (head != null) {
            // 使用位运算左移一位，然后加上当前节点的值
            decimalValue = (decimalValue << 1) | head.val;
            head = head.next;
        }
  
        return decimalValue;
    }
}

📚 方法三：使用 Map 存储 0、1（理解权重计算）

我们可以使用一个 Map 来存储链表中的 0 和 1，然后根据它们的位置计算十进制值。

适用场景 ：当需要多次访问链表节点时（虽然本题不需要），例如需要逆向计算的情况

复杂度分析 ：

时间复杂度：O(2n) → 需要两次完整遍历
空间复杂度：O(n) → 存储所有节点值

public class Solution {
    public int getDecimalValue(ListNode head) {
        Map<Integer, Integer> map = new HashMap<>();
        int index = 0;
        ListNode current = head;
  
        // 将链表中的值存储到 Map 中
        while (current != null) {
            map.put(index++, current.val);
            current = current.next;
        }
  
        int decimalValue = 0;
        int size = map.size();
  
        // 根据位置计算十进制值
        for (int i = 0; i < size; i++) {
            decimalValue += map.get(i) * Math.pow(2, size - i - 1);
        }
  
        return decimalValue;
    }
}

📚 方法四：反转链表（深入理解链表操作）

设计意图：

通过反转链表，将最低有效位变为首位，实现自然权重分配。这种方法虽然增加了代码量，但：

帮助理解链表反转操作
演示了"空间换时间"的另一种思路

复杂度对比 ：

时间复杂度：O(2n) → 反转链表+计算各需一次遍历
空间复杂度：O(1) → 原地反转，无需额外空间

我们也可以先将链表反转，然后从头开始计算十进制值。这种方法虽然稍微复杂一些，但是可以帮助我们更好地理解链表的操作。

public class Solution {
    public int getDecimalValue(ListNode head) {
        // 反转链表
        ListNode reversedHead = reverseList(head);
        int decimalValue = 0;
        int power = 0;
  
        // 遍历反转后的链表
        while (reversedHead != null) {
            decimalValue += reversedHead.val * Math.pow(2, power);
            power++;
            reversedHead = reversedHead.next;
        }
  
        return decimalValue;
    }
  
    // 反转链表的辅助函数
    private ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode current = head;
  
        while (current != null) {
            ListNode next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }
  
        return prev;
    }
}

📚 课后练习

尝试自己编写一个函数，将十进制数转换为链表形式的二进制数。这将是一个很好的练习，帮助你巩固今天所学的知识。📝

希望今天的分享对你有帮助，我们明天再见！👋👋👋

可以按以下步骤思考：

用辗转相除法获取二进制位的逆序序列
创建链表节点时需要从最后得到的余数开始向前构建
注意处理输入为0的特殊情况

力扣每日一题--2025.7.14