Python中链表的求和操作（Sum Lists）
题目描述：
给定两个非空链表，表示两个非负整数。其中每个节点存储该整数的一位数字，并且它们在逆序顺序中排列。将这两个数字相加并返回一个新的链表。
例如，假设这两个数字分别为 342 和 465，则应返回数字 807 的链表表示形式。
链表节点定义：
class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4) 输出：7 -> 0 -> 8 原因：342 + 465 = 807
思路：
遍历两个链表，将对应节点值相加，并生成新的节点存储结果。需要注意的是，若两个链表长度不同，则可以在较短链表末尾补零，使得两个链表长度相等。最后还需要判断最高位相加是否有进位，若有则需要再生成一个节点存储进位。
代码演示：
class Solution: def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode: # 新建空节点，用于存储结果 dummy = ListNode(0) cur = dummy # 用于表示进位 carry = 0 while l1 or l2: # 若链表l1已到末尾，则节点值设为0 x = l1.val if l1 else 0 # 若链表l2已到末尾，则节点值设为0 y = l2.val if l2 else 0 # 计算当前位的和 s = x + y + carry # 更新carry carry = s // 10 # 将s的个位数作为新节点的值 cur.next = ListNode(s % 10) # 将cur指向新生成的节点 cur = cur.next # 遍历两个链表 if l1: l1 = l1.next if l2: l2 = l2.next if carry > 0: # 需要再生成一个节点存储进位 cur.next = ListNode(carry) return dummy.next
代码说明：
新建空节点dummy，用于存储结果。由于需要返回的是新的链表，所以需要在生成新节点时，使用形如cur.next = ListNode(val)的方式，而不能使用cur.val = val的方式。
用x = l1.val if l1 else 0和y = l2.val if l2 else 0的方法，可以避免链表长度不同的情况。
使用carry = s // 10的方法，可以更新进位。至于s % 10，则是为了求当前位的值。
相关文章