【LeetCode每周算法】两数相加

迷南。 2022-08-29 12:49 164阅读 0赞

题目来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/add-two-numbers

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

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

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

**示例 1：**

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

**示例 2：**

输入：l1 = \[0\], l2 = \[0\]  
输出：\[0\]

**示例 3：**

输入：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
 *  题目数据保证列表表示的数字不含前导零

**解法一：**

根据链表特点，直接按顺序遍历，计算对应位的数值，同时记录进位即可。

public class Add {
    
        public static void main(String[] args) {
            Add add = new Add();
            ListNode l1 = new ListNode(1);
            l1.next = new ListNode(2);
            ListNode l2 = new ListNode(9);
            l2.next = new ListNode(8);
    //        l2.next.next = new ListNode(4);
            ListNode listNode = add.addTwoNumbers2(l1, l2);
            System.out.println(listNode);
        }
    
        public ListNode addTwoNumbers2(ListNode l1, ListNode l2) {
            // 定义当前遍历到的节点--可以省略，直接使用l1和l2
            ListNode cur1 = l1;
            ListNode cur2 = l2;
            // 结果：待返回的node
            ListNode node = null;
            // 处理返回链表中，当前节点的下一个节点
            ListNode next = null;
            // 相加后进位数值：8+3=11，则进位1
            int step = 0;
            
            // 这里遍历次数执行定义为1000，因为条件中说明，数值最大不超过100位，也就是链表长度不可能超过100.
            // 这里可以优化，使用while循环，将下面的退出条件放在while条件中
            for (int i = 0; i < 1000; i++) {
                // 当前节点数值
                int val1 = 0;
                int val2 = 0;
    
                if (cur1 != null) {
                    val1 = cur1.val;
                    cur1 = cur1.next;
                }
    
                if (cur2 != null) {
                    val2 = cur2.val;
                    cur2 = cur2.next;
                }
    
                // 当前节点值加进位的数值之和
                int val = val1 + val2 + step;
    
                // 处理进位以及计算当前位置最终值
                step = val / 10;
                val = val - step * 10;
                if (node == null) {
                    node = new ListNode(val);
                    // 记录next，方便给下一个节点关联
                    next = node;
                } else {
                    next.next = new ListNode(val);
                    next = next.next;
                }
    
                // 如果当前节点都为空，且没有进位，则停止
                if (cur1 == null && cur2 == null && step==0) {
                    break;
                }
            }
    
            return node;
        }
    
    }
    
    
    class ListNode {
        int val;
        ListNode next;
    
        ListNode() {
        }
    
        ListNode(int val) {
            this.val = val;
        }
    
        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

**解法二：递归**

递归退出条件：当两个节点都是空的时候退出。  
那如果有任一节点为空，另外一个节点不为空，那我们的节点相加逻辑就会出现空指针异常，在这里直接牺牲空间来满足处理逻辑。  
进位处理：默认在任何一个加数节点上即可，这里放在了l1上

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            if(l1 == null && l2 ==null){
                return null;
            }
            if(l1 == null){
                l1 = new ListNode(0);
            }
            if(l2 == null){
                l2 = new ListNode(0);
            }
            int rval = l1.val + l2.val;
            if(rval >= 10){
                rval = rval % 10;
                if(l1.next != null){
                    l1.next.val+=1;
                }else{
                    l1.next = new ListNode(1);
                }
            }
            return new ListNode(rval, addTwoNumbers(l1.next, l2.next));
        }
    }

[7d87baa243f73bac7930b19529e847c7.png]: /images/20220829/2189578c61b04878897aee1589618b09.png