题目描述
思路解析动画文字版
记牢这条主线:反转让个位在前,从个位一路翻倍进位,最后别忘了收尾那一次进位,再反转回来就是答案。为什么不能直接把链表拼成一个整数算?因为节点最多一万个,这个数会大到任何整型都装不下,只能逐位算。下面从 189 开始。
输入 · 1,8,9 表示 189：先看这条输入链表,从左到右是 1,8,9,表头 1 是最高位、末尾 9 是个位,合起来就是 189。末尾的 null 表示到头了。我们的目标是把它乘以 2,答案应该是 378,后面一步步把这个 378 拼出来。
反转链表 · 个位来到最前面：翻倍是竖式乘法,得从个位算起,可现在个位 9 躲在链表最后。所以第一步把链表整体反转,变成 9,8,1,这样个位 9 就来到了表头,后面从左往右扫就是从低位往高位算,进位也顺着往右带,非常顺手。
开始逐位翻倍 · 进位从 0 起：现在摆开两行看。上面这行是反转后的输入 9,8,1,用一个当前指针从个位开始往右读;下面这行是马上要生成的结果链,现在还是空的。约定一个进位记号,初始是 0。倍数固定是 2。准备好了,读第一位。
读个位 9 · 算 9×2+0=18：当前指针停在个位的 9。这一位算 9 乘 2 加上进位 0,等于 18。它到了两位数,说明这一位会产生进位。把结果拆成个位和进位两部分。
写下 8 · 进位变成 1：把 18 拆开:个位是 8,接到结果链末尾;十位 1 就是要带给下一位的进位。这次进位是 1,下一位要多加 1。结果链现在是 8。上面这一位读过了,置灰,当前指针准备右移。
读十位 8 · 算 8×2+1=17：当前指针停在十位的 8。这一位算 8 乘 2 再加上上一位带来的进位 1,等于 17。它到了两位数,说明这一位会产生进位。把结果拆成个位和进位两部分。
写下 7 · 进位变成 1：把 17 拆开:个位是 7,接到结果链末尾;十位 1 就是要带给下一位的进位。这次进位是 1,下一位要多加 1。结果链现在是 8,7。上面这一位读过了,置灰,当前指针准备右移。
读百位 1 · 算 1×2+1=3：当前指针停在百位的 1。这一位算 1 乘 2 再加上上一位带来的进位 1,等于 3。它还是一位数,这次没有进位。把结果拆成个位和进位两部分。
写下 3 · 进位变成 0：把 3 拆开:个位是 3,接到结果链末尾;十位 0 就是要带给下一位的进位。这次进位是 0,下一位照常算。结果链现在是 8,7,3。上面这一位读过了,置灰,当前指针准备右移。
三位读完 · 进位是 0,无需补节点：输入三位全部读完,收尾要看进位。现在进位是 0,不用再补新节点。结果链此刻是 8,7,3,它是低位在前的顺序,也就是把 378 倒着放。最后一步,只要把它反转回来。
反转结果 · 得到 3,7,8 即 378：把低位在前的结果链 8,7,3 整体反转回来,得到 3,7,8,高位重新回到表头,正好表示 378。189 乘 2 等于 378,和一开始说的答案对上了。这就是主流程:反转、逐位翻倍进位、收尾、再反转。
例二 · 9,9,9 表示 999：再看一个更有意思的例子,9,9,9 表示 999。它每一位都是 9,翻倍时会连续进位,而且最高位也会溢出,正好演示前面说的补最高位那一步。答案应该是 1998。
反转仍是 9,9,9 · 进位从 0 起：9,9,9 是个回文,反转以后还是 9,9,9,但个位在前这一步不能省,规则照旧。摆开两行,进位从 0 起。开始逐位读。
读第一个 9 · 算 9×2+0=18：当前读到第一个 9。算 9 乘 2 加进位 0,等于 18,又是个两位数,还会往上进 1。拆成个位和进位。
写下 8 · 进位仍是 1：个位 8 接到结果链,进位保持为 1。结果链现在是 8。进位继续往下一位带。
读第二个 9 · 算 9×2+1=19：当前读到第二个 9。算 9 乘 2 加进位 1,等于 19,又是个两位数,还会往上进 1。拆成个位和进位。
写下 9 · 进位仍是 1：个位 9 接到结果链,进位保持为 1。结果链现在是 8,9。进位继续往下一位带。
读最高位 9 · 算 9×2+1=19：当前读到最高位 9。算 9 乘 2 加进位 1,等于 19,又是个两位数,还会往上进 1。这是输入的最高位,读完它就要看收尾进位了。拆成个位和进位。
写下 9 · 进位仍是 1：个位 9 接到结果链,进位保持为 1。结果链现在是 8,9,9。注意此刻输入读完了,进位还挂着一个 1,不能丢。
进位=1 · 补一个最高位新节点 1：收尾这一步是最容易漏的。输入三位读完,进位还是 1,说明最高位翻倍溢出了。必须给结果链再补一个节点,值就是这个进位 1。补完结果链变成 8,9,9,1,这就是为什么 999 乘 2 会从三位变成四位。
反转结果 · 得到 1,9,9,8 即 1998：把低位在前的 8,9,9,1 反转回来,得到 1,9,9,8,正好是 1998。刚才补的那个进位 1,反转后落在了表头,成了新的最高位。999 乘 2 等于 1998,一位不差。
回顾 · 进位至多是 1：两个例子回顾一下。189 乘 2 得 378,每位翻倍带着进位往高位走;999 乘 2 得 1998,最高位溢出还补了一个节点。有个规律值得记:每位是 0 到 9,翻倍最多 18,再加上一个进位也就 19,所以进位永远只会是 0 或 1,绝不会更大。抓住反转、逐位翻倍进位、收尾补进位、再反转这四步,这题就稳了。
边界想清:单个 0 原样、5 翻倍溢出补成 1,0、189 翻倍得 378 不增位。
面试重点:反转到个位在前逐位翻倍进位、也可从高位看下一位是否大于等于 5 一遍完成、时间 O(n) 额外空间 O(1)。
参考代码
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 doubleIt(self, head: Optional[ListNode]) -> Optional[ListNode]: def reverse(head): dummy = ListNode() cur = head while cur: next = cur.next cur.next = dummy.next dummy.next = cur cur = next return dummy.next head = reverse(head) dummy = cur = ListNode() mul, carry = 2, 0 while head: x = head.val * mul + carry carry = x // 10 cur.next = ListNode(x % 10) cur = cur.next head = head.next if carry: cur.next = ListNode(carry) return reverse(dummy.next)复杂度
- 时间：O(n)，n 是链表节点数。反转一遍 O(n),逐位翻倍再走一遍 O(n),最后反转回来又 O(n),三段都是线性,合起来随节点数线性增长
- 空间：O(1)，按峰值算,不计返回的结果链。两次反转都是原地改指针,只用常数个指针变量;进位 carry 也是一个数。除了必须建出来的答案链,额外空间是常数
易错点
面试追问把动画讲成自己的话
追问这题的核心做法是什么?
追问有没有不反转链表的更省空间做法?
追问复杂度是多少?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
从链表中移除在数组中存在的节点
LeetCode 3217 · 中等 · 沿着 链表套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题