问题描述

 

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

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

  看到题目，我的第一思路是将链表存储的数还原出来并相加，之后就被 10000000000 教育了，即使将存储数据的数据类型改变依然出错。之后开始改变思路。

链表存储的整数是倒序存储的，那么最后一位必定是 个位，之后的位数依次递增，而相同位置的数是可以相加的，据此我们可以倒序得到一条表示和的链表。

需要考虑的问题：

        1. 进位问题

        2. 链表长度不一

算法：

        设置一个表示进位的变量 preAdd，用于判断是否要+1，

        同时遍历两条链表，将相同位数上的数字相加，相加的数为 v1 + v2 + flag, 链表指定结点存储的 val 值为 ：(v1 + v2 + flag) % 10

        进位为：（v1 + v2 + flag）/ 10; 

        另外，我们需要考虑在循环结束 preAdd = 1 的情况。

ps:  链表的长度不一，循环过程中其中一条链表有可能先结束是变量指向null，我们需要考虑这些情况以便位数相加。

代码 

        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            ListNode node = null;
            ListNode pre = null;
            int preAdd = 0;
            while (l1 != null || l2 != null) {
                int v1 = l1 == null ? 0 : l1.val;
                int v2 = l2 == null ? 0 : l2.val;
                int sum = v1 + v2 + preAdd;
                if (pre == null) {
                    node = pre = new ListNode(sum % 10);
                } else {
                    pre.next = new ListNode(sum % 10);
                    pre = pre.next;
                }
                preAdd = sum / 10;
                /* 向后 */
                if (l1 != null) {
                    l1 = l1.next;
                }
                if (l2 != null) {
                    l2 = l2.next;
                }
            }
            if (preAdd > 0) {
                pre.next = new ListNode(preAdd);
            }
            return node;
        }

            while (l2 != null) {
                int sum = l2.val + preAdd;
                pre.next = new ListNode(sum % 10);
                pre = pre.next;
                preAdd = sum / 10;
                l2 = l2.next;
            }
            if(preAdd > 0){
                pre.next = new ListNode(preAdd);
            }
            return node;

 

执行结果