LeetCode 1290简单链表
二进制链表转整数 图解题解
这道题到底在问什么
链表从表头到表尾,依次是一个二进制数从最高位到最低位的每一位,每个节点只装 0 或 1。请返回这串二进制对应的十进制整数。题目保证链表非空,节点数不超过 30。本节演示 1 0 1 1 0 1 1 这条链表,它就是二进制 1011011,要把它换算成十进制。
- 输入
- head = [1,0,1]
- 输出
- 5(二进制 101)
- 输入
- 本节演示 head = [1,0,1,1,0,1,1]
- 输出
- 91(二进制 1011011)
最优解：一步一步想明白
- 3记牢一套动作:每到一个节点,num 先乘 2 腾位置,再加上这一位。后面每一帧都在套这两步。
- 4上面这条链表有 7 个节点,从左到右依次是 1 0 1 1 0 1 1,最左边的表头是最高位,最右边是最低位,后面跟着 null 表示到头了。开算之前先准备一个累加器 num,现在是 0。接下来从表头开始,一个节点一个节点往后走。
- 5cur 指针停在第 0 个节点,读出这一位是 1。处理它之前,手里已经累计的 num 是 0。
- 6先把 num 左移一位,也就是乘 2,把原来攒下的每一位整体往左挪一格,最低位空出来等着放新位。num 从 0 变成 0。
- 7再把刚读到的这一位 1 填进空出来的最低位,也就是给 num 加上 1。num 变成 1,二进制写法是 1。第 0 个节点处理好了,指针往后挪。
- 8cur 指针停在第 1 个节点,读出这一位是 0。处理它之前,手里已经累计的 num 是 1。
- 9先把 num 左移一位,也就是乘 2,把原来攒下的每一位整体往左挪一格,最低位空出来等着放新位。num 从 1 变成 2。
- 10再把刚读到的这一位 0 填进空出来的最低位,也就是给 num 加上 0。num 变成 2,二进制写法是 10。第 1 个节点处理好了,指针往后挪。
- 11cur 指针停在第 2 个节点,读出这一位是 1。处理它之前,手里已经累计的 num 是 2。
- 12先把 num 左移一位,也就是乘 2,把原来攒下的每一位整体往左挪一格,最低位空出来等着放新位。num 从 2 变成 4。
- 13再把刚读到的这一位 1 填进空出来的最低位,也就是给 num 加上 1。num 变成 5,二进制写法是 101。第 2 个节点处理好了,指针往后挪。
- 14cur 指针停在第 3 个节点,读出这一位是 1。处理它之前,手里已经累计的 num 是 5。
- 15先把 num 左移一位,也就是乘 2,把原来攒下的每一位整体往左挪一格,最低位空出来等着放新位。num 从 5 变成 10。
- 16再把刚读到的这一位 1 填进空出来的最低位,也就是给 num 加上 1。num 变成 11,二进制写法是 1011。第 3 个节点处理好了,指针往后挪。
- 17cur 指针停在第 4 个节点,读出这一位是 0。处理它之前,手里已经累计的 num 是 11。
- 18先把 num 左移一位,也就是乘 2,把原来攒下的每一位整体往左挪一格,最低位空出来等着放新位。num 从 11 变成 22。
- 19再把刚读到的这一位 0 填进空出来的最低位,也就是给 num 加上 0。num 变成 22,二进制写法是 10110。第 4 个节点处理好了,指针往后挪。
- 20cur 指针停在第 5 个节点,读出这一位是 1。处理它之前,手里已经累计的 num 是 22。
- 21先把 num 左移一位,也就是乘 2,把原来攒下的每一位整体往左挪一格,最低位空出来等着放新位。num 从 22 变成 44。
- 22再把刚读到的这一位 1 填进空出来的最低位,也就是给 num 加上 1。num 变成 45,二进制写法是 101101。第 5 个节点处理好了,指针往后挪。
- 23cur 指针停在第 6 个节点,读出这一位是 1。处理它之前,手里已经累计的 num 是 45。
- 24先把 num 左移一位,也就是乘 2,把原来攒下的每一位整体往左挪一格,最低位空出来等着放新位。num 从 45 变成 90。
- 25再把刚读到的这一位 1 填进空出来的最低位,也就是给 num 加上 1。num 变成 91,二进制写法是 1011011。第 6 个节点处理好了,指针往后挪。
- 267 个节点全走完了。每一步都是先乘 2 再加当前位,最后 num 停在 91。对一下:链表 1 0 1 1 0 1 1 就是二进制 1011011,换成十进制正好是 91,答案成立。
⚠️ 容易写错的地方
✗ 错：先把整条链表拼成字符串再转十进制
✓ 对：边走边算,num 每步乘 2 再加当前位
一次遍历加一个整数就够,拼字符串既多占空间又容易写错
✗ 错：方向搞反,把表头当成最低位
✓ 对：表头是最高位,所以让已累计的 num 乘 2,新位补到最低位
每往后一个节点,原来的每一位权重都要翻倍,正好对应乘 2
✗ 错：担心 num 乘 2 加当前位 和 左移再按位或 结果不同
✓ 对：每位非 0 即 1,两种写法完全等价
左移腾出的最低位是 0,加上这一位 和 按位或这一位 都只是把这个 0 填成 0 或 1
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# 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 ansC++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
int getDecimalValue(ListNode* head) {
int ans = 0;
for (; head; head = head->next) {
ans = ans << 1 | head->val;
}
return ans;
}
};Java
import java.util.*;
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
public int getDecimalValue(ListNode head) {
int ans = 0;
for (; head != null; head = head.next) {
ans = ans << 1 | head.val;
}
return ans;
}
}复杂度
时间
O(n)
n 是链表节点数。从表头到表尾只走一遍,每个节点做一次乘 2 加一位的常数运算
空间
O(1)
只用了一个整型累加器 num,没有再开和链表长度成正比的数组或字符串,峰值占用是常数
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 二进制链表转整数 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么从表头开始、每步乘 2 再加当前位就对?+
因为表头是最高位。每往后挪一个节点,原来累计的结果里每一位的权重都要翻一倍,乘 2 正好做这件事;乘完之后最低位空出来,把当前这一位填进去。一路走到最后一位,每一位都恰好被抬到了它应有的权重,num 就是正确的十进制值。
num 乘 2 加当前位 和 参考代码里的 左移一位 再 按位或,有区别吗?+
对 0 和 1 的位没有任何区别。左移一位就是乘 2,会在最低位留下一个 0;此时再加上这一位,或者按位或上这一位,结果一样,都是把那个 0 填成 0 或 1。位运算写法更贴近二进制语义,也更快一点。
空间能做到常数吗?会不会溢出?+
能做到常数空间,全程只用一个整型累加器,不开额外数组或字符串。也不会溢出:题目限定最多 30 个节点,也就是最多 30 位二进制,这个值远在 int 的范围内,用普通 int 就够,不必换 long。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 二进制链表转整数 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。