LeetCode 题解工作台
翻倍以链表形式表示的数字
给你一个 非空 链表的头节点 head ，表示一个不含前导零的非负数整数。 将链表 翻倍 后，返回头节点 head 。 示例 1： 输入： head = [1,8,9] 输出： [3,7,8] 解释： 上图中给出的链表，表示数字 189 。返回的链表表示数字 189 * 2 = 378 。 示例 2…
3
题型
5
代码语言
3
相关题
当前训练重点
中等 · 链表指针操作
答案摘要
我们先将链表翻转，然后模拟乘法运算，最后再将链表翻转回来。 时间复杂度 ，其中 是链表的长度。忽略答案链表的空间消耗，空间复杂度 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 链表指针操作 题型思路
题目描述
给你一个 非空 链表的头节点 head ，表示一个不含前导零的非负数整数。
将链表 翻倍 后，返回头节点 head 。
示例 1：
输入：head = [1,8,9] 输出：[3,7,8] 解释：上图中给出的链表，表示数字 189 。返回的链表表示数字 189 * 2 = 378 。
示例 2：
输入：head = [9,9,9] 输出：[1,9,9,8] 解释：上图中给出的链表，表示数字 999 。返回的链表表示数字 999 * 2 = 1998 。
提示：
- 链表中节点的数目在范围
[1, 104]内 0 <= Node.val <= 9- 生成的输入满足：链表表示一个不含前导零的数字，除了数字
0本身。
解题思路
方法一：翻转链表 + 模拟
我们先将链表翻转，然后模拟乘法运算，最后再将链表翻转回来。
时间复杂度 ，其中 是链表的长度。忽略答案链表的空间消耗，空间复杂度 。
# 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)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) since each node is visited twice during reversal and doubling. Space complexity is O(1) because all operations are in-place without extra data structures. |
| 空间 | O(1) |
面试官常问的追问
外企场景- question_mark
Check if candidate reverses the list to simplify least-significant-digit manipulation.
- question_mark
Watch for correct carry propagation across multiple nodes, especially consecutive 9s.
- question_mark
Notice if candidate maintains O(1) space by avoiding extra stacks or arrays.
常见陷阱
外企场景- error
Failing to reverse the linked list first can complicate carry handling.
- error
Forgetting to add an extra node when a carry remains after the last node.
- error
Incorrectly assuming the list is in least-significant-digit-first order, leading to wrong results.
进阶变体
外企场景- arrow_right_alt
Doubles a number stored in a linked list in reverse order without reversing the list.
- arrow_right_alt
Triple the number represented by the linked list instead of doubling.
- arrow_right_alt
Perform addition of two numbers represented by linked lists using similar pointer traversal.