深知自己目前还没能力做到每日一道算法题，目前先定个目标：每周一道题吧~！也不知道能不能坚持下去，这次刷的是leetcode的第二题 。
距离上次刷题已经过了一个月了吧？~？ (万恶的莫教练把我拖进MC的坑！！！)

题目： 两数相加

题干:

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself

中文翻译：

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

Example:

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

解题思路

我们发现题目给的是一个链表，如果我们把元素依次拿出来整理计算后在填回去，这个过程及代码实现想想都头皮发麻，并且这是道算法题，肯定有巧解的方法。
我们发现链表是从个位开始的，而加法不也是从个位开始加的吗？这时我第一时间想到的就是模拟小学学的竖式计算。
我们简单的分析一下两个数(链表)，得到一下几个问题

注意的点

  1. 当两个数相加大于9时，会发生进位
  2. 两个数长短不一
  3. 两个数相加的和不会超过18
  4. 0和10如何区分表示

有了基本思路，那就开始动手解题：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        # 初始化头节点
        head = ListNode(0)
        l3 = head
        # 进位标志
        carry = 0
        # 跑完两个链表后退出
        while l1 or l2:
            # 当某个链表是空结点时替换成0进行计算
            x = l1.val if l1 else 0 
            y = l2.val if l2 else 0
            # 计算当前位的值
            my_sum = x + y + carry
            carry = my_sum // 10
            l3.next = ListNode(my_sum % 10)
            # 链表操作，指向后一个结点
            l3 = l3.next
            l1 = l1.next if l1 else None
            l2 = l2.next if l2 else None
        # 当最后一次循环时发生进位，则添加一个新结点
        if carry != 0:
            l3.next = ListNode(carry)
        return head.next

结束

  • 刷题可以查缺补漏
  • 不知道说什么了~~ 不能再咕咕咕咕咕了！