2、两数相加(leetCode-2)

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-two-numbers

示例：

image.png

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

输入：l1 = [0], l2 = [0]
输出：[0]

输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

数据结构

    class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

个人对于这种题目，就是简单的走一步看一步。可以从题目中看出，这其实就是简单版的大数相加，相加的结果需要有一个地方来存放，我首先想到的就是用一个List，然后将List的结果转换为ListNode,为什么不直接用ListNode作为结果呢？因为脑子转不过来，这是本人第一次看到这个题目所写：
思路：
1、先将两数相同长度的部分相加
2、对较长数进行进位处理
3、对最后的进位进行处理
4、将结果集转换为ListNode

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int jinwei = 0;
        int result = 0;
        ListNode head = new ListNode();
        List<Integer> res = new ArrayList<>();
        // 两数相加
        while(l1!=null && l2!=null){
            result = l1.val + l2.val + jinwei;
            jinwei = result / 10;
            res.add(result % 10);
            l1 = l1.next;
            l2 = l2.next;
        }
        // 两个数中较大者与进位相加
        while(l1!=null){
            res.add((l1.val + jinwei)%10);
            jinwei = (l1.val + jinwei) / 10; 
            l1 = l1.next;
        }

        while(l2!=null){
            res.add((l2.val + jinwei)%10);
            jinwei = (l2.val + jinwei) / 10; 
            l2 = l2.next;
        }
        // 最终还有进位就装进结果集
        if(jinwei > 0){
            res.add(jinwei);
        }
        
        // 将结果集转换为ListNode
        ListNode current = head;
        for(int i=0 ; i < res.size(); i++){
            current.val = res.get(i);
            if(i!=res.size()-1){
                current.next = new ListNode();
                current = current.next;
            }
        }
        return head;
    }
}

分析上面的代码，给人感觉重复代码太多，而且不够简洁，时间复杂度嘛O(n)还行，空间的话就蚌埠住了。看了官方解答之后，有一个点非常新奇，就是补"0"。位数不够，0来凑，这也是大数相加的核心。。。
话不多说，直接上代码

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(0);
        // 创建一个操作指针
        ListNode current = head;
        int result = 0;
        int jinwei = 0;
        while( l1 != null || l2 != null) {
            int x = l1 == null ? 0 : l1.val;
            int y = l2 == null ? 0 : l2.val;

            result = x + y + jinwei;
            jinwei = result>9?1:0;
            result = result % 10;

            current.next = new ListNode(result);
            current = current.next;

            if(l1!=null){
                l1 = l1.next;
            }

            if(l2!=null){
                l2 = l2.next;
            }
        }

        if(jinwei>0){
            current.next = new ListNode(jinwei);
        }
        //head头部为初始化的0，所以返回head.next
        return head.next;
    }
}

相比之前的方法，该方法将两次循环合并(使用补"0"的方式，这样的话，两个ListNode就是一样长，就能将两次循环合并)，并用ListNode来装结果集。

image.png