Hello Programmer

力扣-两数相加

发表于 更新于 分类于

题目描述

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。请你将两个数相加，并以相同形式返回一个表示和的链表。你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例 1：

1
2
3
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

示例 2：

1
2
输入：l1 = [0], l2 = [0]
输出：[0]

示例 3：

1
2
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

提示：

  • 每个链表中的节点数在范围 [1, 100] 内
  • 0 <= Node.val <= 9
  • 题目数据保证列表表示的数字不含前导零

Python题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        # 初始化
        head = now = ListNode(0)
        sumNum = 0
        # 循环条件
        while l1 or l2 or sumNum//10:
          	# 补0
            l1 = l1 if l1 else ListNode(0)
            l2 = l2 if l2 else ListNode(0)
            sumNum = l1.val + l2.val + sumNum//10
            now.val = sumNum % 10
            l1 = l1.next
            l2 = l2.next
            # 给下一位赋值
            if l1 or l2 or sumNum//10:
                now.next = ListNode(0)
                now = now.next
        return head

这边我之前犯了一个错误（代码如下），head和ll一开始引用同一个对象，当ll被赋为指向对象的next时，而指向对象的next为None，此时若再给ll赋新的对象，原先ll指向的对象的next并不会指向ll指向的新的对象，这两个对象没有任何联系，感觉这个可以用内存来解释。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# head ll 引用同一个对象
head = ll = ListNode(0)
for i in range(10):
    if ll is None:
      	# 此时new的节点和head所指向的节点已经没关系了
        ll = ListNode(0)
    ll.val = i
    # ll变成了None
    ll = ll.next

while head:
    print(head.val)
    head = head.next

看到了一个用递归解题的大佬：

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        val = l1.val + l2.val
        l1 = l1.next if l1.next else ListNode(0)          # 补0
        l2 = l2.next if l2.next else ListNode(0)
        l1.val = l1.val + val//10                         # 满10进1
        if l1.val or l1.next or l2.val or l2.next:        
            next_node = self.addTwoNumbers(l1, l2)
        else:                                             # 0+0 则终止递归
            next_node = None
        return ListNode(val%10,next_node)

自己尝试用递归写：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        l1 = l1 if l1 else ListNode(0)
        l2 = l2 if l2 else ListNode(0)
        sumNum = l1.val + l2.val
        if l1.next or l2.next or sumNum//10:
            if l1.next:
                l1.next.val += sumNum//10
            elif l2.next:
                l2.next.val += sumNum//10
            else:
                l1.next = ListNode(sumNum//10)
            nextNode = self.addTwoNumbers(l1.next, l2.next)
        else:
            nextNode = None
        return ListNode(sumNum % 10, nextNode)

小结

  • 刚刚开始起步刷题，看了别人的代码才有思路
  • 在python中//才是除以某数并向下取整