LeetCode 2. 两数相加

问题

给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。

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

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

示例:

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

思路

链表存储的顺序正好是按照「个十百千」的顺序,与计算加法相似,只要访问每个节点,求和进位即可

需要注意的是:

  1. 遍历的条件:因为题目没有说两个链表一样长,这也合理,比如13 + 1023,也要能够完成计算,所以条件应为两个链表有一个不为None,且不要忽略进位,如果进位存在的话,也要把进位值写到结果链表中;
  2. 输出的结果也是一个链表,最开始我还通过计算直接输出了一个整形...所以每一步的计算结果就直接写到链表中的节点中,且注意,返回的是链表的头;

代码如下:

class Solution:
    """
    input: ListNode1, ListNode2
    output: result ListNode
    """
    def addTwoNumbers(self, l1, l2):
        curr = ListNode(0)
        head = curr
        # 长度也可能不同
        sumnext = sumcurr = 0
        while None != l1 or None != l2 or sumnext != 0:
            if None != l1:
                sumnext += l1.val
                l1 = l1.next
            if None != l2:
                sumnext += l2.val
                l2 = l2.next
            
            sumnext, sumcurr = divmod(sumnext, 10)
            
            curr.next = ListNode(sumcurr)
            curr = curr.next
        
        return head.next

评论

暂无评论