LeetCode 题解工作台
二进制链表转整数
给你一个单链表的引用结点 head 。链表中每个结点的值不是 0 就是 1。已知此链表是一个整数数字的二进制表示形式。 请你返回该链表所表示数字的 十进制值 。 最高位 在链表的头部。 示例 1： 输入： head = [1,0,1] 输出： 5 解释： 二进制数 (101) 转化为十进制数 (5)…
2
题型
10
代码语言
3
相关题
当前训练重点
简单 · 链表指针操作
答案摘要
我们用变量 记录当前的十进制值，初始值为 。 遍历链表，对于每个结点，将 左移一位，然后再或上当前结点的值。遍历结束后， 即为十进制值。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 链表指针操作 题型思路
题目描述
给你一个单链表的引用结点 head。链表中每个结点的值不是 0 就是 1。已知此链表是一个整数数字的二进制表示形式。
请你返回该链表所表示数字的 十进制值 。
最高位 在链表的头部。
示例 1：
输入：head = [1,0,1] 输出：5 解释：二进制数 (101) 转化为十进制数 (5)
示例 2：
输入：head = [0] 输出：0
提示：
- 链表不为空。
- 链表的结点总数不超过
30。 - 每个结点的值不是
0就是1。
解题思路
方法一：遍历链表
我们用变量 记录当前的十进制值，初始值为 。
遍历链表，对于每个结点，将 左移一位，然后再或上当前结点的值。遍历结束后， 即为十进制值。
时间复杂度 ，其中 为链表的长度。空间复杂度 。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def getDecimalValue(self, head: ListNode) -> int:
ans = 0
while head:
ans = ans << 1 | head.val
head = head.next
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for the candidate's ability to understand binary-to-decimal conversion and linked-list manipulation.
- question_mark
Evaluate the solution's efficiency, especially with regard to space complexity when using extra data structures.
- question_mark
Observe whether the candidate considers both iterative and recursive solutions for this problem.
常见陷阱
外企场景- error
Not efficiently updating the result while traversing the list (e.g., skipping bit shifting or not properly accounting for the most significant bit).
- error
Misunderstanding the linked-list structure and failing to correctly traverse each node.
- error
Using extra space like arrays or strings without considering the impact on space complexity.
进阶变体
外企场景- arrow_right_alt
Modify the problem to handle lists with mixed 0's and 1's with a different bit-order or additional manipulations.
- arrow_right_alt
Extend the problem to handle binary numbers represented with negative or floating point values.
- arrow_right_alt
Implement the solution for cases where the linked list contains more than 30 nodes or follows a different structure (e.g., doubly linked).