1290-二进制链表转整数

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:29 2023-09-13 16:06:29 Updated    

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

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

示例 1：

![](https://assets.leetcode-cn.com/aliyun-lc-
upload/uploads/2019/12/15/graph-1.png)

**输入：** 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

提示：

  • 链表不为空。
  • 链表的结点总数不超过 30。
  • 每个结点的值不是 0 就是 1。

方法一：模拟

由于链表中从高位到低位存放了数字的二进制表示，因此我们可以使用二进制转十进制的方法，在遍历一遍链表的同时得到数字的十进制值。

以示例 1 中给出的二进制链表为例：

以下用 (n)_2 表示 n 是二进制整数。

(101)_2 = 1 \times 2^2 + 0 \times 2^1 + 1 \times 2^0

链表的第 1 个节点的值是 1，这个 1 是二进制的最高位，在十进制分解中，1 作为系数对应的 2^2 的指数是 2，这是因为链表的长度为 3。我们是不是有必要一定要先知道链表的长度，才可以确定指数 2 呢？答案是不必要的。

  • 每读取链表的一个节点值，可以认为读到的节点值是当前二进制数的最低位；
  • 当读到下一个节点值的时候，需要将已经读到的结果乘以 2，再将新读到的节点值当作当前二进制数的最低位；
  • 如此进行下去，直到读到了链表的末尾。
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int getDecimalValue(ListNode* head) {
        ListNode* cur = head;
        int ans = 0;
        while (cur != nullptr) {
            ans = ans * 2 + cur->val;
            cur = cur->next;
        }
        return ans;
    }
};
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int getDecimalValue(ListNode head) {
        ListNode curNode = head;
        int ans = 0;
        while (curNode != null) {
            ans = ans * 2 + curNode.val;
            curNode = curNode.next;
        }
        return ans;
    }
}
[sol1-Python3]
1
2
3
4
5
6
7
8
class Solution:
    def getDecimalValue(self, head: ListNode) -> int:
        cur = head
        ans = 0
        while cur:
            ans = ans * 2 + cur.val
            cur = cur.next
        return ans

复杂度分析

  • 时间复杂度：O(N)，其中 N 是链表中的节点个数。

  • 空间复杂度：O(1)。

 Comments
On this page
1290-二进制链表转整数
  1. 方法一：模拟