class Solution: def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]: head = point = ListNode(0) carry = 0 while l1 or l2: new_point = ListNode(0) if not l1: # 如果l1为空,则只考虑l2的值和进位carry sum = l2.val + carry new_point.val = sum % 10 carry = sum // 10 l2 = l2.next elif not l2: # 如果l2为空,则只考虑l1的值和进位carry sum = l1.val + carry carry = sum // 10 new_point.val = sum % 10 l1 = l1.next else: # 如果l1和l2都不为空,则考虑l1和l2的值以及进位carry sum = l1.val + l2.val + carry carry = sum // 10 new_point.val = sum % 10 l1 = l1.next l2 = l2.next point.next = new_point point = point.next if carry: # 如果最后carry有值,需要再添加一个节点 point.next = ListNode(carry) return head.next 这个代码的时间复杂度太高了,你能帮我优化一下吗?
时间: 2024-02-10 13:05:08 浏览: 122
add-two-numbers
这段代码的时间复杂度为O(max(m,n)),其中m和n分别为l1和l2的长度。我们可以通过将两个链表的值相加转化为数字相加,然后将结果再转化为链表来优化时间复杂度。
以下是优化后的代码:
```
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
num1, num2 = "", ""
# 将两个链表的值转化为数字
while l1:
num1 += str(l1.val)
l1 = l1.next
while l2:
num2 += str(l2.val)
l2 = l2.next
# 将转化后的数字相加
total = int(num1[::-1]) + int(num2[::-1])
# 将相加后的数字转化为链表
dummy = ListNode(0)
cur = dummy
for digit in str(total)[::-1]:
cur.next = ListNode(int(digit))
cur = cur.next
return dummy.next
```
这段代码的时间复杂度为O(m+n),其中m和n分别为l1和l2的长度,优化了原始代码的时间复杂度。
阅读全文