本文最后更新于191 天前,其中的信息可能已经过时,如有错误请发送邮件到xieyuchen3@gmail.com

我的写法是这样
输入: l1=[2,4,3], l2=[5,6,4]
↓
反转: [3,4,2], [4,6,5]
↓
转数字: 342, 465
↓
相加: 807
↓
转链表: [8,0,7]
↓
再反转: [7,0,8]
class Solution:
def addTwoNumbers(self, l1, l2):
def reverse_list(head):
prev = None
current = head
while current:
t = current.next
current.next = prev
prev = current
current = t
return prev
def link_to_number(head):
num = 0
current = head
while current:
num = num * 10 + current.val # 123 = 1*100 + 2*10 + 3
current = current.next
return num
def number_to_link(num):
if num == 0:
return ListNode(0)
head = None
while num > 0:
g = num % 10
node = ListNode(g)
node.next = head
head = node
num //= 10
return head
fanzhuan1 = reverse_list(l1)
fanzhuan2 = reverse_list(l2)
bianli1 = link_to_number(fanzhuan1)
bianli2 = link_to_number(fanzhuan2)
he = bianli1 + bianli2
result = number_to_link(he)
final_result = reverse_list(result)
return final_result
标准答案不用第一次反转直接逆位
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def addTwoNumbers(self, l1, l2):
"""
标准解法:逐位相加,处理进位
时间复杂度: O(max(m, n)),m 和 n 分别是两个链表的长度
空间复杂度: O(max(m, n)),新链表的长度最多为 max(m, n) + 1
"""
# 创建虚拟头节点,简化代码
dummy = ListNode(0)
current = dummy
carry = 0 # 进位
# 同时遍历两个链表,直到都为空且没有进位
while l1 or l2 or carry:
# 获取当前位的值,如果链表为空则为 0
val1 = l1.val if l1 else 0
val2 = l2.val if l2 else 0
# 计算当前位的和(包括进位)
total = val1 + val2 + carry
# 计算当前位的值和新的进位
carry = total // 10
digit = total % 10
# 创建新节点并连接到结果链表
current.next = ListNode(digit)
current = current.next
# 移动到下一个节点
l1 = l1.next if l1 else None
l2 = l2.next if l2 else None
# 返回结果链表的头节点(跳过虚拟头节点)
return dummy.next
