No.2 两数之和 (Medium)

题目描述

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

例如：

解释：
因为是逆序保存的，所以2->4->3表示数字342, 同理得到465
342 + 465 = 807, 因此得到7->0->8

注意，两个链表并不一定长度相同，即可能20 + 300 = 320。

思路

首先理解为什么要用倒序表示一个数，因为链表只能从头结点开始遍历，分别表示个，十，百，千 … 因此只有倒序时，才符合我们的数学计算规则，从个位开始计算和，然后说十位，百位 …

该题的几个难点：

1. 进位如何处理
2. 不同长度的链表如何处理

难点1：进位如何处理

if (有进位) {
    sum = value1 + value2 + 进位;
} else {
    sum = value1 + value2;
}
// 简化版本
int carry = 0;
while () {
    sum = value1 + value2 + carry;
    carry = sum / 10;
    sum = sum % 10;
}

此为，如果 两个链表都遍历完了，最高位仍然有进位，需要再最高位补1

难点2： 不同长度的链表如何处理

对短链表的高位补0，例如240 + 32 = 240 + 032

小技巧

在处理链表问题时，通常会在头结点(Head)前面初始化一个dummy node, 主要原因是链表通常会涉及到指针的移动，例如在遍历之后，指针指向了最后一个结点，那么怎么返回该链表的头结点呢？技巧就是添加一个dummy node指向链表的头结点，那么最后只需要返回dummy.next即可。

代码

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
           // current首先指向dummy, 在遍历过程中仅移动current, 不再移动dummy
        ListNode current = dummy;
        // 初始化carry为0
        int carry = 0;
        // 循环停止的条件为两个链表都为null
        while (l1 != null || l2 != null) {
            // 当l1或者l2不为空时，value值即结点的值
            // 为空时，value值为0，就相当于是短的链表已经遍历到最后了，指向null了
            int value1 = l1 == null ? 0 : l1.val;
            int value2 = l2 == null ? 0 : l2.val;
            // 求和，该和可能大于10，产生新的carry
            int sum = value1 + value2 + carry;
            // 计算新的carry，例如，sum = 16, carry = 16 / 10 = 1;
            // Java中，两个整数相除，商为整数，直接丢弃了小数位
            carry = sum / 10;
            // 对sum取余得到新的sum, sum = 16, sum = 16 % 10 = 6;
            sum = sum % 10;
            // current的next指向新的结点
            current.next = new ListNode(sum);
            // current指向新结点
            current = current.next;
            // 移动l1和l2
            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }    
        }
        // 如果都遍历完了，仍然有进位，需要最后补上进位结点
        // 事实上，两个个位数想加，carry最大也只会说1
        // 例如 999 + 999 即便每一位都是最大值，每一位都有进位，最高位也是9 + 9 + 1 = 19
        // 最高位的进位也不会超过1
        if (carry != 0) {
            current.next = new ListNode(carry);
        }
        return dummy.next;
    }
}