【LeetCode每日一题】——1290.二进制链表转整数

一【题目类别】

• 链表

二【题目难度】

• 简单

三【题目编号】

• 1290.二进制链表转整数

四【题目描述】

• 给你一个单链表的引用结点 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

六【解题思路】

• 如果学过计算机组成原理，那么这道题就没有难度，正常模拟就可以，其实就是一个反推的过程
• 我们按照题目示例1（1->0->1）来举例

5 / 2 = 2 余 1
2 / 2 = 1 余 0
1 / 2 = 0 余 1
得到二进制数101，如果要得到原始十进制数，只需要反推即可：商 * 2（除数） + 余数：
0 * 2 + 1 = 1
1 * 2 + 0 = 2
2 * 2 + 1 = 5
这样就可以得到二进制数对应的十进制数
1
2
3
4
5
6
7
8

• 按照以上过程操作就可以得到结果
• 最后返回结果即可

七【题目提示】

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

八【时间频度】

• 时间复杂度：$O(n)$，其中$n$为链表的长度
• 空间复杂度：$O(1)$

九【代码实现】

1. Java语言版

package LinkedList;

/**
 * @Author: IronmanJay
 * @Description: 1290.二进制链表转整数
 * @CreateTime: 2022-12-06  13:10
 */
public class p1290_ConvertBinaryNumberInALinkedListToInteger {

    int val;
    p1290_ConvertBinaryNumberInALinkedListToInteger next;

    public p1290_ConvertBinaryNumberInALinkedListToInteger(int val) {
        this.val = val;
    }

    public p1290_ConvertBinaryNumberInALinkedListToInteger(int val, p1290_ConvertBinaryNumberInALinkedListToInteger next) {
        this.val = val;
        this.next = next;
    }

    public static void main(String[] args) {
        p1290_ConvertBinaryNumberInALinkedListToInteger node1 = new p1290_ConvertBinaryNumberInALinkedListToInteger(1);
        p1290_ConvertBinaryNumberInALinkedListToInteger node2 = new p1290_ConvertBinaryNumberInALinkedListToInteger(0);
        p1290_ConvertBinaryNumberInALinkedListToInteger node3 = new p1290_ConvertBinaryNumberInALinkedListToInteger(1);
        node1.next = node2;
        node2.next = node3;
        int res = getDecimalValue(node1);
        System.out.println("res = " + res);
    }

    public static int getDecimalValue(p1290_ConvertBinaryNumberInALinkedListToInteger head) {
        p1290_ConvertBinaryNumberInALinkedListToInteger p = head;
        int res = 0;
        while (p != null) {
            res = res * 2 + p.val;
            p = p.next;
        }
        return res;
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

2. C语言版

#include

struct ListNode
{
	int val;
	struct ListNode *next;
};

int getDecimalValue(struct ListNode* head)
{
	struct ListNode* p = head;
	int res = 0;
	while (p != NULL)
	{
		res = res * 2 + p->val;
		p = p->next;
	}
	return res;
}

/*主函数省略*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

十【提交结果】

1. Java语言版
   

2. C语言版