LeetCode刷题之HOT100之两数相加

2024/5/27 大家早上好呀，昨晚没睡好，四个小时不到，估计是太兴奋了。昨天去长乐十七孔、下沙赶海啦。远看沙滩上的人群就像一根根木桩矗立在浅滩上，走近些，才发现都佝偻着腰，两只手在沙地淘金（摸花蛤）。放几张图

图一、十七孔水库附近

图二、十七孔——右侧礁石是妈祖像

图三、追风筝的人——为你千千万万遍

图四、新能源花蛤捕捉器

图五、黄昏落日

准备做题的，我突然想到还有一张雨后彩虹

图六、雨后彩虹

图片只能是图片，是某个夜晚翻开相册的回忆。只有亲身体会，站在铺满黑绿青苔，镶嵌贝类的礁石上，带有咸腥的狂烈海风扑在身上，一阵一阵的浪花扑打过来，那一刻是自由的。做题

1、题目描述

2、逻辑分析

题目是两数相加，数字的表示使用了链表的线性结构，且使用逆序方式存储。我的大致思路：两个链表同时遍历，相加，逢十进位。看看题解怎么说。官方题解给出的解法跟我想的差不多，但是我想的不够具体。

进位部分：取一个变量来表示进位，每次相加的和表示为：sum = （n1 + n2 + jinWei）% 10。这样如果相加结果小于10，则不会有变化。大于等于10，那么就需要进位。具体还是看代码更清晰一些：

3、代码演示

 public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // 初始化头节点和尾节点，开始时都为null  
        ListNode head = null, tail = null;
        // 进位，初始化为0  
        int jinWei = 0;
        // 当两个链表中的任一链表不为空时，继续循环 
        while(l1 != null || l2 != null){
            // 获取l1的当前节点的值，如果l1为空，则取0
            int n1 = l1 != null? l1.val: 0;
            // 获取l2的当前节点的值，如果l2为空，则取0
            int n2 = l2 != null? l2.val: 0;
            // 计算当前两个节点值的和加上进位
            int sum = n1 + n2 + jinWei;
            // 如果头节点为空（即刚开始创建第一个节点时）
            if(head == null){
                // 创建新节点，值为sum的个位数，并将头节点和尾节点都指向它 
                head = tail = new ListNode(sum % 10);
            }else{
                // 否则，创建新节点，并将它连接到尾节点的后面 
                tail.next = new ListNode(sum % 10);
                // 更新尾节点为新的尾节点  
                tail = tail.next;
            }
            // 更新进位为sum的十位数
            jinWei = sum / 10;
            // 如果l1不为空，则移动到l1的下一个节点 
            if(l1 != null){
                l1 = l1.next;
            }
            // 如果l2不为空，则移动到l2的下一个节点
            if(l2 != null){
                l2 = l2.next;
            }
        }
        // 如果最后还有进位（即两个链表的最高位相加后有进位）
        if(jinWei > 0 ){
            // 创建一个新节点表示进位，并将其连接到尾节点的后面
            tail.next = new ListNode(jinWei);
        }
        // 返回头节点，即新的链表的开始位置  
        return head;
    }
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
30
31
32
33
34
35
36
37
38
39
40
41
42

根据代码，我们用一个实际例子来论证：

时间复杂度：O(max(m,n))，空间复杂度;O(1)。

太困了，眯了一会醒来再做的，写blog挺费事费力的，但是会让思路更清晰，加油！