题目描述
思路解析动画文字版
记牢一套动作:每到一个节点,num 先乘 2 腾位置,再加上这一位。后面每一帧都在套这两步。
总览 · 表头是最高位,num 从 0 起步：上面这条链表有 7 个节点,从左到右依次是 1 0 1 1 0 1 1,最左边的表头是最高位,最右边是最低位,后面跟着 null 表示到头了。开算之前先准备一个累加器 num,现在是 0。接下来从表头开始,一个节点一个节点往后走。
读第 0 个节点 · 这一位是 1：cur 指针停在第 0 个节点,读出这一位是 1。处理它之前,手里已经累计的 num 是 0。
先左移一位 · num 乘 2：先把 num 左移一位,也就是乘 2,把原来攒下的每一位整体往左挪一格,最低位空出来等着放新位。num 从 0 变成 0。
再加这一位 · num + 1：再把刚读到的这一位 1 填进空出来的最低位,也就是给 num 加上 1。num 变成 1,二进制写法是 1。第 0 个节点处理好了,指针往后挪。
读第 1 个节点 · 这一位是 0：cur 指针停在第 1 个节点,读出这一位是 0。处理它之前,手里已经累计的 num 是 1。
先左移一位 · num 乘 2：先把 num 左移一位,也就是乘 2,把原来攒下的每一位整体往左挪一格,最低位空出来等着放新位。num 从 1 变成 2。
再加这一位 · num + 0：再把刚读到的这一位 0 填进空出来的最低位,也就是给 num 加上 0。num 变成 2,二进制写法是 10。第 1 个节点处理好了,指针往后挪。
读第 2 个节点 · 这一位是 1：cur 指针停在第 2 个节点,读出这一位是 1。处理它之前,手里已经累计的 num 是 2。
先左移一位 · num 乘 2：先把 num 左移一位,也就是乘 2,把原来攒下的每一位整体往左挪一格,最低位空出来等着放新位。num 从 2 变成 4。
再加这一位 · num + 1：再把刚读到的这一位 1 填进空出来的最低位,也就是给 num 加上 1。num 变成 5,二进制写法是 101。第 2 个节点处理好了,指针往后挪。
读第 3 个节点 · 这一位是 1：cur 指针停在第 3 个节点,读出这一位是 1。处理它之前,手里已经累计的 num 是 5。
先左移一位 · num 乘 2：先把 num 左移一位,也就是乘 2,把原来攒下的每一位整体往左挪一格,最低位空出来等着放新位。num 从 5 变成 10。
再加这一位 · num + 1：再把刚读到的这一位 1 填进空出来的最低位,也就是给 num 加上 1。num 变成 11,二进制写法是 1011。第 3 个节点处理好了,指针往后挪。
读第 4 个节点 · 这一位是 0：cur 指针停在第 4 个节点,读出这一位是 0。处理它之前,手里已经累计的 num 是 11。
先左移一位 · num 乘 2：先把 num 左移一位,也就是乘 2,把原来攒下的每一位整体往左挪一格,最低位空出来等着放新位。num 从 11 变成 22。
再加这一位 · num + 0：再把刚读到的这一位 0 填进空出来的最低位,也就是给 num 加上 0。num 变成 22,二进制写法是 10110。第 4 个节点处理好了,指针往后挪。
读第 5 个节点 · 这一位是 1：cur 指针停在第 5 个节点,读出这一位是 1。处理它之前,手里已经累计的 num 是 22。
先左移一位 · num 乘 2：先把 num 左移一位,也就是乘 2,把原来攒下的每一位整体往左挪一格,最低位空出来等着放新位。num 从 22 变成 44。
再加这一位 · num + 1：再把刚读到的这一位 1 填进空出来的最低位,也就是给 num 加上 1。num 变成 45,二进制写法是 101101。第 5 个节点处理好了,指针往后挪。
读第 6 个节点 · 这一位是 1：cur 指针停在第 6 个节点,读出这一位是 1。处理它之前,手里已经累计的 num 是 45。
先左移一位 · num 乘 2：先把 num 左移一位,也就是乘 2,把原来攒下的每一位整体往左挪一格,最低位空出来等着放新位。num 从 45 变成 90。
再加这一位 · num + 1：再把刚读到的这一位 1 填进空出来的最低位,也就是给 num 加上 1。num 变成 91,二进制写法是 1011011。第 6 个节点处理好了,指针往后挪。
完成 · 答案 91：7 个节点全走完了。每一步都是先乘 2 再加当前位,最后 num 停在 91。对一下:链表 1 0 1 1 0 1 1 就是二进制 1011011,换成十进制正好是 91,答案成立。
边界都一个套路:不管最高位是 0 还是 1、链表多长,都从 num 等于 0 起步,每步乘 2 再加当前位。
面试重点:表头是最高位所以每步乘 2、位运算与乘加等价、整条只用一个 int 不溢出。
参考代码
from __future__ import annotationsfrom 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 = rightclass 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 = nextclass Solution: def getDecimalValue(self, head: ListNode) -> int: ans = 0 while head: ans = ans << 1 | head.val head = head.next return ans复杂度
- 时间：O(n)，n 是链表节点数。从表头到表尾只走一遍,每个节点做一次乘 2 加一位的常数运算
- 空间：O(1)，只用了一个整型累加器 num,没有再开和链表长度成正比的数组或字符串,峰值占用是常数
易错点
面试追问把动画讲成自己的话
追问为什么从表头开始、每步乘 2 再加当前位就对?
追问num 乘 2 加当前位 和 参考代码里的 左移一位 再 按位或,有区别吗?
追问空间能做到常数吗?会不会溢出?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
两数相加
LeetCode 2 · 中等 · 沿着 链表套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题