【LeetCode 算法练习】“两数相加(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

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

Python 算法 LeetCode 两数相加 解答 技术 Add Two Numbers
本文更新于