🎉LeetCode2. 两数相加 - 《算法》

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

:::info 1、规律：链表A和链表B的第i个节点的和为Sum=Ai.val + Bi.val + carry(进位)，新的第i个节点的值应该为Sum%10，产生的新的进位为sum/10。 ::: :::danger 2、分析：链表A和链表B从第1个节点开始求和，当某一个链表的已有节点遍历完之后，另一个链表还有节点，那么遍历完的链表可以看做后面还有值为0的节点（因为这里是相加，任何一个数加0，还是这个数），如果是相乘，那么遍历完的链表可以看做后面是值为1的节点，因为任何一个数乘以1，还是这个数。 ::: :::success 3、步骤：① 设置初始进位carry为0，la纸箱链表A的头结点，lb指向链表B的头结点；由于不知道A和B那个链表更长，每一次都更新链表A和链表B的节点，设置res变量记录返回哪个链表；由于可能最后跳出循环的时候，还有进位，也就是carry不为0，所以设置last变量记录返回链表的最后一个节点在哪；
② 从头开始遍历链表A和B，循环条件为链表A当前节点(la)不为空或者链表B当前节点(lb)不为空，那么跳出循环的原因是A和B都遍历结束了；
③ 确定valA和valB的值，根据la和lb是否为空
④ sum = carry+valA+valB；
⑤ 更新carry的值：sum/10;
⑥ 如果la不为空，更新la的值为：sum%10；更新res为链表A；更新last为la；更新la为la.next;
⑦ 如果lb不为空，更新lb的值为：sum%10；更新res为链表B；更新last为lb；更新lb为lb.next;
⑧ 如果carry不为0，创建新的节点，节点的val初始值为carry，last指向该节点。
⑨ 返回链表res。 ::: :::info 4、代码：
刚开始自己实现的 :::

/**
 * 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) {
        ListNode h1 = l1;
        ListNode h2 = l2;
        int carry = 0;
        int len1 = 0, len2 = 0;
        ListNode node = new ListNode();
        while(h1 != null){
            len1++;
            h1 = h1.next;
        }
        while(h2 != null){
            len2++;
            h2 = h2.next;
        }
        if(len1 >= len2){
            h1 = l1;
            h2 = l2;
        }else{
            h1 = l2;
            h2 = l1;
        }
        while(h1 != null && h2 != null){
            int val = h1.val + h2.val + carry;
            carry = val / 10;
            int rest = val % 10;
            h1.val = rest;
            if(h1.next == null){
                node = h1;
            }
            h1 = h1.next;
            h2 = h2.next;
        }
        while(h1 != null){
            int val = h1.val + carry;
            carry = val / 10;
            int rest = val % 10;
            h1.val = rest;
            if(h1.next == null){
                node = h1;
            }
            h1 = h1.next;
        }
        if(carry != 0){
            ListNode n = new ListNode(carry);
            node.next = n;
        }
        if(len1 >= len2){
            return l1;
        }else{
            return l2;
        }
    }
}

:::info 4、代码：
看了题解之后自己实现的 :::

/**
 * 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) {
        ListNode h1 = l1;
        ListNode h2 = l2;
        int carry = 0;
        ListNode res = l1;
        ListNode last = l1;
        while(h1 != null || h2 != null){
            int valA = h1 == null ? 0 : h1.val;
            int valB = h2 == null ? 0 : h2.val;
            int sum = carry + valA + valB;
            carry = sum / 10;
            if(h1 != null){
                h1.val = sum % 10;
                res = l1;
                last = h1;
                h1 = h1.next;
            }
            if(h2 != null){
                h2.val = sum % 10;
                res = l2;
                last = h2;
                h2 = h2.next;
            }
        }
        if(carry > 0){
            ListNode node = new ListNode(carry);
            last.next = node;
        }
        return res;
    }
}