难度: Medium
给你一个 非空 链表的头节点 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 <= 90 本身。运行时间: 169 ms
内存: 18.2 MB
# 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]:
s = ""
root = head
while root:
s += str(root.val)
root = root.next
ss = ""
val = 0
for i in range(1,len(s)+1):
num = int(s[-i])
a = num * 2 + val
val,num = divmod(a,10)
ss = str(num) + ss
if val:
ss = str(val) + ss
node = ListNode(int(ss[0]))
head1 = node
for i in range(1,len(ss)):
node.next = ListNode(int(ss[i]))
node = node.next
return head1
这个题解的整体思路是首先将链表中的数字转换成字符串，然后将这个字符串表示的整数翻倍。具体步骤如下：1. 遍历链表，将链表中的数值拼接成一个完整的数字字符串。2. 从字符串的最后一个字符（即最低位）开始，每个字符代表的数字都翻倍，并处理进位。3. 如果最高位处理完后还有进位，则将进位添加到结果字符串的最前面。4. 将得到的翻倍后的字符串转换回链表形式。
时间复杂度: O(n)
空间复杂度: O(n)
# 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]:
s = ""
root = head
while root:
s += str(root.val) # 将链表数字拼接为字符串
root = root.next
ss = ""
val = 0 # 初始化进位为0
for i in range(1,len(s)+1):
num = int(s[-i]) # 从最低位开始处理
a = num * 2 + val # 翻倍并加上进位
val,num = divmod(a,10) # 更新进位和当前位
ss = str(num) + ss # 将当前位添加到结果字符串
if val:
ss = str(val) + ss # 处理最后的进位
node = ListNode(int(ss[0])) # 创建新链表的头节点
head1 = node
for i in range(1,len(ss)):
node.next = ListNode(int(ss[i])) # 依次创建链表的后续节点
node = node.next
return head1
在题解中，链表的数字被转换成字符串，然后进行计算。这种方法本质上是将整数的每一位以字符形式存储，因此不受普通整型变量大小的限制。Python的字符串可以处理非常长的序列，且整数类型（int）在Python中是动态大小的，可以处理任意大小的整数，只受限于机器的内存。因此，对于超大整数值，这种方法是安全的，不会超出处理范围。
题解中通过逐位处理链表中的数字，每位数字翻倍后加上前一位的进位来进行计算。具体操作是通过`num * 2 + val`实现，其中`num`是当前位的数字，`val`是上一位的进位值。使用`divmod(a, 10)`函数可以同时得到当前位的结果和新的进位值，`divmod(a, 10)`会返回两个值，第一个是除以10的商，即新的进位，第二个是余数，即当前位的结果。这种方法可以准确地处理每一位的翻倍和进位，包括边界情况。
如之前所述，Python的整数类型（int）是动态大小的，可以扩展以存储任意大的整数。因此，使用`num * 2 + val`进行计算是安全的，不会发生整数溢出。每次计算后，通过`divmod`函数处理上限为10的除法和求余，确保结果始终在合理的范围内，适合转换回链表的单个节点。这确保了算法在所有情况下都是有效和安全的，无需担心整数溢出。