LeetCode 链表:2. 两数相加

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

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

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-two-numbers
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法一:累加之后取反(不可行)

首先看到这道题,先想到了一种解法,那就是把链表的数字都取出来,然后再取反,相加,最后反过来输出生成新的链表:

例如是先取出 val1 = 243;val2 = 564; 返过来获得值为:val1 = 342,val2 = 465;相加之后得到807,然后再反过来生成新的链表.

 public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int v1 = 0;
        int v2 = 0;
        ListNode tempHead = new ListNode(0);
        ListNode temp = tempHead;
        while(l1 != null){
            v1 = v1 * 10 + l1.val;
            l1 = l1.next;
        }
        while(l2 != null){
            v2 = v2 * 10 + l2.val;
            l2 = l2.next;
        }
        int resultV1 = reverseVal(v1);
        int resultV2 = reverseVal(v2);
        int result = resultV1 + resultV2;
        while(result > 0){
            ListNode node = new ListNode(result % 10);
            result = result / 10;
            tempHead.next = node;
            tempHead = tempHead.next;
        }
        return temp.next;
    }
    
    /**
     * @description : 数字取反,243 -> 342 
     * @params : [val]
     * @return : int 
     * @author : zhengyao 
     * @date : 2020/3/29 
     */
    public static int reverseVal(int val){
        int result = 0;
        while(val > 0){
            result = val % 10 + result * 10;
            val = val / 10;
        }
        return result;
    }

但是这种值对数值类型的上限有要求,过不了所有的testcase,因为会超出int类型与long类型的上限导致溢出,所以这种方式只对小数值型有效

解法二:链表直接累加法

首先就将两者的值一一累加,主要需要考虑的是如何进位,因为两者相加有可能需要进位,而因为是逆序存储,所以进位的数值直接给后面的数值加1即可,注意:这里要考虑最后一位相加时会有进位的情况产生,例如[1],[99],这里结果应该为[0,0,1],最后需要判断是否有进位,有的话需要额外多连接一个结点.

public static ListNode addTwoNumbers2(ListNode l1, ListNode l2) {
        ListNode temp = new ListNode(0);
        ListNode tempHead = temp;
        int carry = 0;
        while (l1 != null || l2 != null) {
            int v1 = l1 == null ? 0 : l1.val;
            int v2 = l2 == null ? 0 : l2.val;
            int sum = v1 + v2 + carry;
            carry = sum / 10;
            temp.add(sum % 10);
            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
        }
        if (carry > 0) {
            temp.add(carry);
        }
        return tempHead;
    }