前言
Algorithms + Data Structures = Programs.
————Pascal之父 Nicklaus Wirth
算法 + 数据结构 = 程序
坚持刷算法题，变得更强！
题目及详解
解析
解题目标：我们最后返回的是一个新链表，这个链表的逆序等于本来两个链表逆序相加，所以被称为两数相加。 难度中等，且听细细道来~
思路：看到题目是不是有点不知所措，难道我应该把链表的表头开始存下来，存到数组里或存到哪里，然后再让其相加，再逆序一下得到新数组或其他？
没那么麻烦。想想你算加法的时候咋算的？是不是从个位数开始相加呀？那你看这个这俩链表的表头，不就是你要的个位数吗？
重点来了，从表头开始相加，存到一个新链表里，重要的是如果表头两个数相加超过10咋办？那你是不是要进1，比如表头为5+7，那你是不是（5+7）%10 = 2，把2存到新链表表头，把（5+7）/10 = 1，把1进入下一位相加，问题就迎刃而解。
代码实现步骤详解
接下来我们看一下题目所给的代码
/*** 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; }* }*/classSolution { publicListNodeaddTwoNumbers(ListNodel1, ListNodel2) { } }
上面给了一个ListNode类，里面有几个方法，下面也给了俩参数l1和l2，那么我们就可以用这两个参数代表两个链表各自的表头，然后用l1.next和l2.next调用各自链表接下来的数。
接下来，我们要创建三个变量，一个dummy作为新链表，一个curr作为新链表指针，一个carry用来接收5+6这种需要向下一位进1的情况。
classSolution { publicListNodeaddTwoNumbers(ListNodel1, ListNodel2) { ListNodedummy=newListNode(); ListNodecurr=dummy; intcarry=0; } }
接下来我们的工作就是遍历两个链表让他们从表头开始相加，不由自主地想到需要用到一个循环，但什么时候结束呢？ 既然l1和l2用来指向两个链表每一位，那么我们就可以说当两个链表都指向空的时候，循环结束。
classSolution { publicListNodeaddTwoNumbers(ListNodel1, ListNodel2) { ListNodedummy=newListNode(); ListNodecurr=dummy; intcarry=0; while(l1!=null||l2!=null){ intx=l1==null?0 : l1.val; inty=l2==null?0 : l2.val; intsum=x+y+carry; curr.next=newListNode(sum%10); curr=curr.next; carry=sum/10; if (l1!=null) l1=l1.next; if (l2!=null) l2=l2.next; } } }
int x和int y那里是最早从C语言中就见过的表达式，他的意思是如果l1等于空，则把0给x，不为空，则把l1.val（题目给的链表数）赋给x。当然y同理。
然后最后两个if语句，举个栗子，2+12，第一次循环l1指向的数据2，然后判断l1不为空，则l1指向下一位，下一位就是空了，第二次循环的时候就会判断为空，不再继续改变l1的指向。
当然，退出循环之后别忘记还有个carry，比如456+789，加到百位的时候是不是又要进1？但你l1和l2都指向空了，那就另行判断carry是否为0，不为0，记得加1。最后返回新链表dummy。
完整解题代码
classSolution { publicListNodeaddTwoNumbers(ListNodel1, ListNodel2) { ListNodedummy=newListNode(); ListNodecurr=dummy; intcarry=0; while(l1!=null||l2!=null){ intx=l1==null?0 : l1.val; inty=l2==null?0 : l2.val; intsum=x+y+carry; curr.next=newListNode(sum%10); curr=curr.next; carry=sum/10; if (l1!=null) l1=l1.next; if (l2!=null) l2=l2.next; } if (carry!=0)curr.next=newListNode(carry); returndummy.next; } }
