LeetCode第二题：两数相加

ゞ浴缸里的玫瑰 2023-10-04 17:06 12阅读 0赞

### LeetCode第二题：两数相加 ###

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只存储一位数字。

请你将两个数相加，并以相同形式返回一个表示和的链表

举例：

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

提示：每个链表的节点数在范围\[1, 100\]内，0 <= Node.val <= 9

#### 需要涉及的知识 ####

##### 1、链表 #####

链表又分为单向链表，双向链表，环形链表，关于Java数据结构-链表详情见[数据结构-链表-java实现][-_-java]

##### 2、链表的相加 #####

因为输入的两个链表都属于是逆序的存储结构，所以两个链表的同一位置的数字可以直接相加

##### 3、解决思路 #####

要达到的结果：  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA54mn56CB5paH_size_18_color_FFFFFF_t_70_g_se_x_16]

##### 开胃小菜： #####

我们完全可以将两个链表分别求出各个节点的值对应的位数之和，因为是逆序存储的，所以这一步并不难，只需要在第n次循环时将节点值乘以10的n次方即可，最后将数值相加。

public double getNodeToNum(Node head){
        
            Node ptr = head.getNext();
            double total = 0.0;
            double pow = 0.0;
            while (ptr != null){
        
                System.out.println("链表：" + ptr.getNum());
                total = total + ptr.getNum() * Math.pow(10.0,pow);
                ptr = ptr.getNext();
                pow ++;
            }
            return total;
        }

两个链表都是这样操作之后会得到最终的结果，然后再将结果创建成链表即可。虽然过程比较蠢，但是好歹也是可以完成的，毕竟**完成比完美重要**。

***这样虽然可以得解，方法蠢是一个方面，另一个方面就是它不是该题想要考察我们的方向***

##### 正经解法： #####

**因为该题目中存储的过程是逆序的，所以可以通过遍历两个链表的节点，相加生成新的链表，在这个过程中考虑到节点相加中进位的处理**

**因为在实际中可能会存在链表长度不相同的情况，所以在每次循环之前都要判断链表是否为空，如果有一个为空，则将其赋值为0**

// 取出该节点的值，如果为空，就是取0
    int a = l1.getNext() == null ? 0 : l1.getNext().getNum();
    int b = l2.getNext() == null ? 0 : l2.getNext().getNum();

以该题为例

##### 在第一步需要将3和4相加 #####

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA54mn56CB5paH_size_20_color_FFFFFF_t_70_g_se_x_16]

// other表示进位，要在循环外定义
    int other = 0;
    // 两个链表的两位相加
    int sum = a + b + other;
    // 大于十进位
    other = sum / 10;
    // 进位之后剩下的为余数，就建立节点放在res之后
    sum = sum % 10;

##### 第二步： #####

存在进位的就会保留进位值，在下一次的循环中加在上一位  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA54mn56CB5paH_size_20_color_FFFFFF_t_70_g_se_x_16 1]

##### 第三步： #####

因为在上一位存在这进步，所以这里会加上上一次的进位，然后看本次是否有进位，再次更新进位的值  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA54mn56CB5paH_size_18_color_FFFFFF_t_70_g_se_x_16 1]

// 两个链表的两位相加
    int sum = a + b + other;

##### 第四步 #####

如果对于该题，到了第三步就已经结束了，但是在实际中，可能在这步还存在这进步没有处理，所以在最后要判断是否依然存在进位，然后将进位当作节点加入链表

// 如果还有进位，增加一个节点
    if (other == 1) cur.setNext(new Node(1));

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA54mn56CB5paH_size_16_color_FFFFFF_t_70_g_se_x_16]

到这里，这道题就已经解决了，总代码

Node类：

class Node {
        
        private int num = 0;
        private Node next = null;
    
        public Node(int num){
        
            this.num = num;
        }
        public Node(){
        
    
        }
    
        public int getNum() {
        
            return num;
        }
    
        public void setNum(int num) {
        
            this.num = num;
        }
    
        public Node getNext() {
        
            return next;
        }
    
        public void setNext(Node next) {
        
            this.next = next;
        }
    }

实现代码

private Node addTwoNumbers(Node l1, Node l2){
        
    
            Node res = new Node(); // 存放结果
            Node cur = res; //res的尾指针
    
            int other = 0;  // 表示进位
            while(l1.getNext() != null || l2.getNext() != null){
        
                // 取出该节点的值，如果为空，就是取0
                int a = l1.getNext() == null ? 0 : l1.getNext().getNum();
                int b = l2.getNext() == null ? 0 : l2.getNext().getNum();
    
                // 两个链表的两位相加
                int sum = a + b + other;
                // 大于十进位
                other = sum / 10;
                // 进位之后剩下的为余数，就建立节点放在res之后
                sum = sum % 10;
    
                cur.setNext(new Node(sum));
                cur = cur.getNext();
    
                // 将l1和l2分别下移，下移之前要判断是否为空
                if (l1.getNext() != null) l1 = l1.getNext();
                if (l2.getNext() != null) l2 = l2.getNext();
            }
            // 如果还有进位，增加一个节点
            if (other == 1) cur.setNext(new Node(1));
            return res;
        }

测试代码：

public static void main(String[] args) {
        
            leetcode02 ele = new leetcode02();
            // 由列表转换为代码
            List<Integer> node1 = Arrays.asList(2,4,3);
            List<Integer> node2 = Arrays.asList(5, 6, 4);
            
            // 创建链表
            Node node11 = ele.createNode(node1);
            Node node22 = ele.createNode(node2);
            Node res = ele.addTwoNumbers(node11, node22);
            ele.getNode(res);
        }

[-_-java]: https://blog.csdn.net/weixin_46429290/article/details/121537704
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA54mn56CB5paH_size_18_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/4437c957395e4f8ba6b34db1a13c3e5a.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA54mn56CB5paH,size_18,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA54mn56CB5paH_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/2ce057d5cda54b39a7fa5d07b06157e0.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA54mn56CB5paH,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA54mn56CB5paH_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/fba7e9bb5cd14501b957401632031304.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA54mn56CB5paH,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA54mn56CB5paH_size_18_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/c8713c997bb44ad88ebd8b1bd9505ffd.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA54mn56CB5paH,size_18,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA54mn56CB5paH_size_16_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/0af6db53d81d43c6ace1bd8c1729af75.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA54mn56CB5paH,size_16,color_FFFFFF,t_70,g_se,x_16