如何使用Python实现链表的链表元素相加（Add Two Numbers）
链表是一种数据结构，由多个节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针。链表元素相加指的是将两个链表中对应位置的元素相加，如果相加的结果大于等于10，则向下一位进一。
最简单的方法是使用循环遍历两个链表，依次将当前节点的值相加并记录进位。如果其中一个链表已经遍历完但另一个链表还有剩余，则将剩余节点和进位相加即可。如果最后一位相加后还有进位，需要在结果链表中添加一个值为1的节点。
以下是Python代码示例：
class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next class Solution: def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode: carry = 0 # 进位 dummy = ListNode(0) # 定义一个哑节点 curr = dummy # 定义一个指针，用来操作每一个新建的节点 while l1 or l2: # 如果当前节点为空，则值为0 x = l1.val if l1 else 0 y = l2.val if l2 else 0 # 计算当前位的值和进位 s = carry + x + y carry = s // 10 curr.next = ListNode(s % 10) # 操作指针 curr = curr.next if l1: l1 = l1.next if l2: l2 = l2.next # 如果最后一位相加后还有进位，需要在结果链表中添加一个值为1的节点 if carry > 0: curr.next = ListNode(carry) return dummy.next
针对本题，还可以使用递归来实现，代码如下：
class Solution: def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode: if not l1: return l2 if not l2: return l1 # 计算当前位的值和进位 s = l1.val + l2.val carry = s // 10 curr = ListNode(s % 10) # 递归计算下一位，并处理进位 curr.next = self.addTwoNumbers(l1.next, l2.next) if carry: curr.next = self.addTwoNumbers(ListNode(carry), curr.next) return curr
以上是Python实现链表相加的代码示例。
相关文章