“两数相加（Add Two Numbers）”问题的 Python3 解答

题目描述

给定两个非空链表来表示两个非负整数。位数按照逆序方式存储，它们的每个节点只存储单个数字。将两数相加返回一个新的链表。

你可以假设除了数字 0 之外，这两个数字都不会以零开头

示例

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

测试用例

[2,4,3]
[5,6,4]

[1]
[9,9]

[5]
[5]

[0]
[7,3]

[9,9]
[9]

解题思路

遍历链表，按节点两两相加，有进位将进位加到下一个节点。

解题思路很简单，此题被标记为中等难度，是因为：

1. 数据结构是链表；
2. 两个链表长度不一定相等，尤其是有进位情况下的处理需考虑。

解答

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        l3 = l1

        while l1 != None or l2 != None:
            sum = l1.val + l2.val
            l1.val = sum % 10

            if sum >= 10:
                if l1.next != None:
                    l1.next.val = l1.next.val + 1

                    if l1.next.val >= 10 and l2.next == None:
                        l2.next = ListNode(0)
                else:
                    l1.next = ListNode(1)

            else:
                if l1.next == None and l2.next != None:
                    l1.next = ListNode(0)

            if l2.next == None:
                break

            l1 = l1.next
            l2 = l2.next

        return l3

算法分析

上述算法通过一次遍历完成，没有用单独的变量存储 carry 值。两个链表同节点相加的结果最大为 9 + 9 + 1 = 19，所以结果链表中对应节点的值永远可以用(l1[index] + l2[index] + carry) % 10来得到。

上述算法将进位 carry 计入到了下一位中。具体解题过程为

1. 用新变量 l3 保留对 l1 的引用
2. l1 和 l2 对应节点做加法
3. 有进位且 l1 有下一节点的情况下，将进位加入到 l1 的下一个节点；l1 没有下一个节点就给 l1 添加一个值为 1 的节点；没有进位执行步骤4
4. l1 没有下一个节点了，但是 l2 还有下一个节点，就给 l1 添加一个值为 0 的节点
5. 3 或 4 步骤执行完毕，如果 l2 没值了，就跳出循环，返回 l3，原题得解；否则将 l1 和 l2 移动一个节点，执行步骤2

中文官网的题目地址：两数相加