引言

本次学习主要分为基础结构的认识，算法的解释，以及对代码的执行框架进行描述
本文章题解是对官方题解的描述，程序非本人书写，仅供学习使用

题目：两数相加

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

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

你可以假设除了数字 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
题目数据保证列表表示的数字不含前导零

来源：力扣（LeetCode）

题目引用类以及答题模板

 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
       
}

基础结构认识

通过对题目所建立的类可以看出本题是一个典型的处理链表的题,然后我们分析题干：

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。

• 解题思路

1.我们通过解决方案所调用类可以知道L1，L2实际上是由两个链表所组成的集合，因此我们可以通过直接对一个集合对象的访问从而输出整个集合的数。这里就与我们学习到的整形数组很相似。
2.通过题目所演示的实例可以看出这个本题的两数相加可以近似理解为一种加法的镜像方式，也就是说我们平常在一个位上面加法的进位值需要加到比这个位高一个位的地方，但是本题的进位值则加到比这个位低一个位的地方，也就是可以理解为说L1，L2链表每个位按顺序加减如果存在有进位的情况就加到低一个位的值上

image.png

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.
题目解释可能会把你绕晕，所以建议用我的方式理解

3.我们可以通过建立两个对象，一个用来固定输出集合的对象和判断L1、L2是否为零，一个用来记录所有位数的相加，这里我们将两个对象先设置为head和tail(figure)。

程序结构分析

image.png

通过使用UML图我们对基础的计算有了一定的认识，但是我们还需要考虑到进位、空值的情况。

• 进位
  我们可以通过一个参数实现进位的判断然后在下一个位数进行加法时判断是否进行进位，假如最后一位还会进位，则继续续写figure.next
• 空值
  也就是L1或者L2无法实现对应相加的情况，我们可以在相加之前对L1或者L2的val值进行条件判断，如果不存在则赋值为0，反之继续,直到L1和L2的val值都不存在时结束。

代码书写

• 建立对象，进位判断值，每一位的加法结果

ListNode head = null；//初始输出集合表头
ListNode tail = null；
int carry=0;
int sum=0;//每一位的加法结果

• 实现对L1,L2数据的遍历，以及加法运算，进位判断

while (l1 != null || l2 != null) {
            int n1 = l1 != null ? l1.val : 0;
            int n2 = l2 != null ? l2.val : 0;
            int sum = n1 + n2 + carry;
            if (head == null) {
                head = tail = new ListNode(sum % 10);//把head的值固定tail相当于续写,理解为对象头指针
            } else {
                tail.next = new ListNode(sum % 10);//链表操作，tail.next.val=sum%10,这时已经为tail.next开辟了一个空间
                tail = tail.next;//类似于tail.val=sum % 10;但不同的是这时tail.next=null，但是不完全正确，后面解释
            }
            carry = sum / 10;//判断进位
           //为了使程序更加高效，已经结束遍历的数组不需要进行下一步的寻找，所以需要进行条件判断
            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
        }

这里我们通过一个小测试对链表进行描述

package Listcode;

public class Test {
    public static void main(String[] args) {
        ListNode head=null;
        ListNode L1=new ListNode(1);
        head=L1;//固定头对象
        L1.next=new ListNode(2);//同时head.next=new ListNode(2);
        L1=L1.next;//相当于L1.val=2,L1.next=null
        System.out.println(L1==L1.next);//L1和L2.next并不是一个空间,但是可以通过L1进行访问
        System.out.println(L1.val+"\t"+L1.next+"\t"+head.val+"\t"+head.next.val);
    }

}

输出结果
false
2 null 1 2
但这个只能对小部分进行描述，这里我们再添加一个

package Listcode;

public class Test {
    public static void main(String[] args) {
        ListNode head=null;
        ListNode L1=new ListNode(1);
        head=L1;
        L1.next=new ListNode(2);
        L1=L1.next;
        System.out.println(L1);
        L1.next=new ListNode(2);
        L1=L1.next;
        System.out.println(L1);
        System.out.println(L1==L1.next);//并不是一个空间
        System.out.println(L1.val+"\t"+L1.next+"\t"+head.val+"\t"+head.next.val+"\t"+head.next.next.val);
    }

}

Listcode.ListNode@4554617c
Listcode.ListNode@74a14482
false
2 null 1 2 2

不难看出每一次的L1.val都在变化，并且每一个L1都不是同一个储存地址，所以对于代码

L1.next=new ListNode(2);
L1=L1.next;

我们可以知道对于第一次理解是错误的，因为这样理解的话就会使tail的空间永远不变，而实际上我们通过测试链表发现每一次通过对L1.next的赋值，以及L1=L1.next，都会影响L1的地址，也就是L1实际的储存位置会发生改变，这也就导致了每一次输出L1的地址都会与前面不同，那么这个地址是L1.next的地址吗？

tail = tail.next;//类似于tail.val=sum % 10;但不同的是这时tail.next=null，但是不完全正确，后面解释

我们通过head对这个说法进行证明：

package Listcode;

public class Test {
    public static void main(String[] args) {
        ListNode head=null;
        ListNode L1=new ListNode(1);
        head=L1;
        System.out.println("L1");
        System.out.println(L1);
        L1.next=new ListNode(2);
        System.out.println("第一个节点"+L1.next);
        L1=L1.next;
        System.out.println(L1);
        System.out.println(L1.next);
        L1.next=new ListNode(2);
        System.out.println("第二个节点"+L1.next);
        L1=L1.next;
        System.out.println(L1);
        System.out.println(L1==L1.next);//并不是一个空间
        System.out.println(L1.val+"\t"+L1.next+"\t"+head.val+"\t"+head.next.val+"\t"+head.next.next.val);
        System.out.println("head");
        System.out.println(head);
        System.out.println(head.next);
        System.out.println(head.next.next);
    }

}

L1
Listcode.ListNode@1540e19d
第一个节点next:Listcode.ListNode@677327b6
Listcode.ListNode@677327b6
L1更新后nextnull
第二个节点next:Listcode.ListNode@14ae5a5
Listcode.ListNode@14ae5a5
false
2 null 1 2 2
head
Listcode.ListNode@1540e19d
Listcode.ListNode@677327b6
Listcode.ListNode@14ae5a5

讲到这里我们又可以对之前的解释进行更加精确的判断。
可以发现head链表表每一个子表都记录了每次L1变化的地址，并指向了它。而且我们可以确定每一次L1=L1.next 相当于更新了L1，它的地址也与旧的L1.next所单独开辟出来的空间所储存的位置相同,但是更新后的L1.next将不再存在值，大家可以理解它为相较于旧的L1，它是L1.next.next（但实际上不存在，因为L1无法调用并不存在的值，而且L1已经更新）

L1.next = new ListNode(1);
L1 = L1.next;
L1.next = new ListNode(2);
L1 = L1.next;

至此我们还剩最后一个问题没有解决——head如何得到每一个更新后的L1。

我们知道L1.next.next并不存在但是head.next.next存在，这是因为L1在赋值时进行了更新，但是head并没有。head是最初的L1，可以理解为表头，head是始终不变的，也不会随着L1的更新而变化，所以head.next就相当于更新一次的L1，以此类推……

总结

链表的基础运作方式我们通过不断的实验得出了比较数据化的结论，对于Leecode两数相加的题我们在明白程序运作的同时，我们也要明白所运用的基础知识，这样才能更好的应用它。