题目

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

提示

• 每个链表中的节点数在范围 [1, 100] 内
• 0 <= Node.val <= 9
• 题目数据保证列表表示的数字不含前导零

思路

最先我的想法是暴力求解，先把链表中所有的节点值倒序拿出，然后组成一个Integer类型的整数值，相加之后再倒序拿出结果集的每一位数字形成一个新的链表，但事实证明太耍小聪明了。

        错误：因为Integer类型的精度问题，导致如果链表的位数超出Integer类型的范围的时候就会出现精度缺失的问题，使用Long类型和Double类型同样会出现精度问题，因此暴力求解法不成立。以下为我写的暴力求解法的代码(错误解法不附上思路)。

/**
  * @author: LoungeXi
  **/
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if(l1.val==0){
            return l2;
        }
        if(l2.val==0){
            return l1;
        }
        double result = add(l1);
        result += add(l2);
        if(result<10){
            return new ListNode((int)result);
        }
        ListNode listNode = new ListNode(0, null);
        ListNode tempListNode = listNode;
        while (((result - (result % 10)) / 10)!=0) {
            System.out.println(result);
            tempListNode.val = ((int) result % 10);
            tempListNode.next = new ListNode((((int) result - ((int) result % 10)) / 10) % 10);
            tempListNode = tempListNode.next;
            result = (result - (result % 10)) / 10;
        }
        return listNode;
    }

    public double add(ListNode listNode) {
        double result = 0.0;
        int count = 0;
        while (listNode != null) {
            result += (listNode.val * Math.pow(10, count++));
            listNode = listNode.next;
        }
        return result;
    }

新的思路

既然暴力求解法不行，只能使用传统的链表方法，同时也更加简单。全程思路在代码演示中给出。

/**
  * @author: LoungeXi
  **/
public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // 指向头指针 作为用于返回的指针
        ListNode prev = new ListNode(0);
        // 可移动指针
        ListNode cur = prev;
        // 进位指针
        int carry = 0;
        // 因为是逆序链表 所以相对的直接相加的值在正序的情况下不受影响，当 l1 和 l2 不为空时循环继续
        while (l1 != null || l2 != null) {
            // 获取链表节点的值，如果节点为空则将值赋值为 0 ，保证链表有相同的位数。
            int x = l1 != null ? l1.val : 0;
            int y = l2 != null ? l2.val : 0;
            // 将两个同位节点的值相加再加上进位的值，作为结果值，进位值一开始为 0 ，因为一开始加的时候是正序的时候的个位
            int sum = x + y + carry;
            // 计算进位值，若 x + y + carry > 10 则 carry 赋值为 1 ， 因为 x + y + carry < 20 ，所已 carry 的值永远为 0 或 1
            carry = sum / 10;
            // 计算当前位数的值 这句代码意思是如果进位了就将 sum 赋值为他的个位上的数，没有进位则还是原来的数
            sum = sum % 10;
            // 将值加入结果集
            cur.next = new ListNode(sum);
            cur= cur.next;
            // 继续计算
            if(l1!=null){
                l1=l1.next;
            }
            if(l2!=null){
                l2=l2.next;
            }
        }
        // 最后两个节点如果 x + y + carry > 10 ，则需要进位，此时继续给 cur 指定一个 val 为 1 的后继节点即可
        if(carry==1){
            cur.next= new ListNode(1);
        }
        // 返回的是 prev 的后继节点，因为 prev 指向的是头指针，其本身的 val 值为 0 ，我们都是在他的后继节点进行操作，数据结构基础
        return prev.next;
    }
}