跳至主要內容

1290. 二进制链表转整数


1290. 二进制链表转整数

🟢   🔖  链表 数学  🔗 力扣open in new window LeetCodeopen in new window

题目

Given head which is a reference node to a singly-linked list. The value of each node in the linked list is either 0 or 1. The linked list holds the binary representation of a number.

Return the decimal value of the number in the linked list.

The most significant bit is at the head of the linked list.

Example 1:

Input: head = [1,0,1]

Output: 5

Explanation: (101) in base 2 = (5) in base 10

Example 2:

Input: head = [0]

Output: 0

Constraints:

  • The Linked List is not empty.
  • Number of nodes will not exceed 30.
  • Each node's value is either 0 or 1.

题目大意

给你一个单链表的引用结点 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. 初始化结果 num 为 0。
  2. 从链表头开始遍历链表 head,直到 head 为空。
  3. 模拟二进制数位移操作:
    • 每访问一个节点,就将当前结果 num 左移一位(num << 1),再加上当前节点的值(head.val)。
    • 这种方式相当于动态地将二进制数从左向右累加。

复杂度分析

  • 时间复杂度O(n),其中 n 是链表的长度,遍历链表一次。
  • 空间复杂度O(1),只使用了常量级变量。

代码

/**
 * @param {ListNode} head
 * @return {number}
 */
var getDecimalValue = function (head) {
	let num = 0;
	while (head) {
		num = (num << 1) | head.val; // 左移一位加当前节点值
		head = head.next; // 移动到下一个节点
	}
	return num;
};