题目：给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
思路：同时遍历两个链表，将对应节点的值相加，并记录进位值，如果循环到有一个链表的节点为null时，就用0和另一个链表节点的值相加，直到两个链表的节点都为null。时间复杂度O(m+n),空间复杂度O(1)。
需要注意的是，当循环退出时，还要判断一次进位值是否为1，如果为1要再向上进一位。
class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { //定义一个前节点，每次循环将当前节点变为前节点 ListNode previousNode = new ListNode(0); //将初始化的前节点赋值给一个头节点，用于保存最前面的节点 ListNode head = previousNode; //十进制 int ary = 10; //初始化进位值为0 int carry = 0; while (l1 != null || l2 != null) { //判断l1、l2是否为null，为null就假定当前的val值为0 int x = l1 == null ? 0 : l1.val; int y = l2 == null ? 0 : l2.val; //计算当前位的值 int value = (x + y + carry) % ary; //计算进位值 carry = (x + y + carry)/ary; //新建当前节点并赋值给前节点的next previousNode.next = new ListNode(value); //将前节点赋值为当前节点，方便进行下次循环 previousNode = previousNode.next; //如果l1、l2不为null，遍历到下一个节点 l1 = l1 == null ? null : l1.next; l2 = l2 == null ? null : l2.next; } //注意最后l1、l2都为null时，while循环退出，但如果前一次有进位的情况 if (carry == 1) { previousNode.next = new ListNode(1); } //返回头节点的第二个节点，保存个位数值的节点 return head.next; } }