翻倍以链表形式表示的数字 图解题解

这道题到底在问什么

输入

head = [1,8,9]

输出

[3,7,8]

输入

head = [9,9,9]

输出

[1,9,9,8]

最优解：一步一步想明白

1. 3记牢这条主线:反转让个位在前,从个位一路翻倍进位,最后别忘了收尾那一次进位,再反转回来就是答案。为什么不能直接把链表拼成一个整数算?因为节点最多一万个,这个数会大到任何整型都装不下,只能逐位算。下面从 189 开始。
2. 4目标:189 乘 2先看这条输入链表,从左到右是 1,8,9,表头 1 是最高位、末尾 9 是个位,合起来就是 189。末尾的 null 表示到头了。我们的目标是把它乘以 2,答案应该是 378,后面一步步把这个 378 拼出来。
3. 5反转到个位在前翻倍是竖式乘法,得从个位算起,可现在个位 9 躲在链表最后。所以第一步把链表整体反转,变成 9,8,1,这样个位 9 就来到了表头,后面从左往右扫就是从低位往高位算,进位也顺着往右带,非常顺手。
4. 6进位=0 · 倍数=2现在摆开两行看。上面这行是反转后的输入 9,8,1,用一个当前指针从个位开始往右读;下面这行是马上要生成的结果链,现在还是空的。约定一个进位记号,初始是 0。倍数固定是 2。准备好了,读第一位。
5. 7个位 ×2 = 18当前指针停在个位的 9。这一位算 9 乘 2 加上进位 0,等于 18。它到了两位数,说明这一位会产生进位。把结果拆成个位和进位两部分。
6. 8进位=1 · 结果 8把 18 拆开:个位是 8,接到结果链末尾;十位 1 就是要带给下一位的进位。这次进位是 1,下一位要多加 1。结果链现在是 8。上面这一位读过了,置灰,当前指针准备右移。
7. 9十位 ×2 = 17当前指针停在十位的 8。这一位算 8 乘 2 再加上上一位带来的进位 1,等于 17。它到了两位数,说明这一位会产生进位。把结果拆成个位和进位两部分。
8. 10进位=1 · 结果 8,7把 17 拆开:个位是 7,接到结果链末尾;十位 1 就是要带给下一位的进位。这次进位是 1,下一位要多加 1。结果链现在是 8,7。上面这一位读过了,置灰,当前指针准备右移。
9. 11百位 ×2 = 3当前指针停在百位的 1。这一位算 1 乘 2 再加上上一位带来的进位 1,等于 3。它还是一位数,这次没有进位。把结果拆成个位和进位两部分。
10. 12进位=0 · 结果 8,7,3把 3 拆开:个位是 3,接到结果链末尾;十位 0 就是要带给下一位的进位。这次进位是 0,下一位照常算。结果链现在是 8,7,3。上面这一位读过了,置灰,当前指针准备右移。
11. 13收尾 · 进位=0输入三位全部读完,收尾要看进位。现在进位是 0,不用再补新节点。结果链此刻是 8,7,3,它是低位在前的顺序,也就是把 378 倒着放。最后一步,只要把它反转回来。
12. 14答案 378把低位在前的结果链 8,7,3 整体反转回来,得到 3,7,8,高位重新回到表头,正好表示 378。189 乘 2 等于 378,和一开始说的答案对上了。这就是主流程:反转、逐位翻倍进位、收尾、再反转。
13. 15目标:999 乘 2再看一个更有意思的例子,9,9,9 表示 999。它每一位都是 9,翻倍时会连续进位,而且最高位也会溢出,正好演示前面说的补最高位那一步。答案应该是 1998。
14. 16进位=0 · 倍数=29,9,9 是个回文,反转以后还是 9,9,9,但个位在前这一步不能省,规则照旧。摆开两行,进位从 0 起。开始逐位读。
15. 179 ×2 = 18当前读到第一个 9。算 9 乘 2 加进位 0,等于 18,又是个两位数,还会往上进 1。拆成个位和进位。
16. 18进位=1 · 结果 8个位 8 接到结果链,进位保持为 1。结果链现在是 8。进位继续往下一位带。
17. 199 ×2 = 19当前读到第二个 9。算 9 乘 2 加进位 1,等于 19,又是个两位数,还会往上进 1。拆成个位和进位。
18. 20进位=1 · 结果 8,9个位 9 接到结果链,进位保持为 1。结果链现在是 8,9。进位继续往下一位带。
19. 219 ×2 = 19当前读到最高位 9。算 9 乘 2 加进位 1,等于 19,又是个两位数,还会往上进 1。这是输入的最高位,读完它就要看收尾进位了。拆成个位和进位。
20. 22进位=1 · 结果 8,9,9个位 9 接到结果链,进位保持为 1。结果链现在是 8,9,9。注意此刻输入读完了,进位还挂着一个 1,不能丢。
21. 23补进位 · 结果 8,9,9,1收尾这一步是最容易漏的。输入三位读完,进位还是 1,说明最高位翻倍溢出了。必须给结果链再补一个节点,值就是这个进位 1。补完结果链变成 8,9,9,1,这就是为什么 999 乘 2 会从三位变成四位。
22. 24答案 1998把低位在前的 8,9,9,1 反转回来,得到 1,9,9,8,正好是 1998。刚才补的那个进位 1,反转后落在了表头,成了新的最高位。999 乘 2 等于 1998,一位不差。
23. 25进位只会是 0 或 1两个例子回顾一下。189 乘 2 得 378,每位翻倍带着进位往高位走;999 乘 2 得 1998,最高位溢出还补了一个节点。有个规律值得记:每位是 0 到 9,翻倍最多 18,再加上一个进位也就 19,所以进位永远只会是 0 或 1,绝不会更大。抓住反转、逐位翻倍进位、收尾补进位、再反转这四步,这题就稳了。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

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 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)

#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:
    ListNode* doubleIt(ListNode* head) {
        head = reverse(head);
        ListNode* dummy = new ListNode();
        ListNode* cur = dummy;
        int mul = 2, carry = 0;
        while (head) {
            int x = head->val * mul + carry;
            carry = x / 10;
            cur->next = new ListNode(x % 10);
            cur = cur->next;
            head = head->next;
        }
        if (carry) {
            cur->next = new ListNode(carry);
        }
        return reverse(dummy->next);
    }

    ListNode* reverse(ListNode* head) {
        ListNode* dummy = new ListNode();
        ListNode* cur = head;
        while (cur) {
            ListNode* next = cur->next;
            cur->next = dummy->next;
            dummy->next = cur;
            cur = next;
        }
        return dummy->next;
    }
};

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 ListNode doubleIt(ListNode head) {
        head = reverse(head);
        ListNode dummy = new ListNode();
        ListNode cur = dummy;
        int mul = 2, carry = 0;
        while (head != null) {
            int x = head.val * mul + carry;
            carry = x / 10;
            cur.next = new ListNode(x % 10);
            cur = cur.next;
            head = head.next;
        }
        if (carry > 0) {
            cur.next = new ListNode(carry);
        }
        return reverse(dummy.next);
    }

    private ListNode reverse(ListNode head) {
        ListNode dummy = new ListNode();
        ListNode cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = dummy.next;
            dummy.next = cur;
            cur = next;
        }
        return dummy.next;
    }
}

复杂度

面试官可能追问