题目

https://leetcode-cn.com/problems/add-two-numbers/
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
image.png

思路

image.png
考虑用变量carry，保存进位。
长度不一致的话，短的链表后面加上0替代加上原来链表结点的值。

代码

  1. # Definition for singly-linked list.
  2. # class ListNode:
  3. #     def __init__(self, x):
  4. #         self.val = x
  5. #         self.next = None
  7. class Solution:
  8.     def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
  9.         # 用一个新的链表表示进位
  10.         ans = dummy_node = ListNode(0) # inplace
  11.         tmp_node = ListNode(0)
  13.         carry = 0
  14.         while l1 or l2:
  15.             x = l1.val if l1 else 0
  16.             y = l2.val if l2 else 0
  18.             tmp_sum = x + y + carry
  19.             dummy_node.next = ListNode(tmp_sum % 10)
  20.             carry = tmp_sum // 10
  21.             dummy_node = dummy_node.next
  22.             if l1: l1 = l1.next
  23.             if l2: l2 = l2.next
  25.         if carry > 0:
  26.             dummy_node.next = ListNode(carry)
  28.         return ans.next