题目描述
两个非空的链表逆序表示两个非负的整数，每个节点只存储一位数字，例如：数组567表示为7->6->5。求两数相加的和，结果返回一个新链表逆序表示。
示例：
输入：1->2->3 和 7->5->2
输出：8->7->5
原因：321+257=578
解析
考察重点：链表的遍历
从链表的第一个结点起，依次访问每个结点的next引用遍历下一个结点，直到链表结尾结点，此结点next引用为null。
注意要点：
- 同时遍历两个链表，相对应位置的结点表示的数字相加；
- 两个链表长短不一致时，短链表遍历完全后继续遍历长链表，直到两个链表全部遍历；
- 两个数字加和结果可能产生进位，需要定义单独的变量保存进位值；
- 每次计算完一个结点后挂在表示结果的新链表尾部。
技巧：
- 访问短链表结束之后，继续遍历长链表时，短链表加数可用0代替；
- 结果可以预先定义头节点（next引用指向链表的第一个元素，但本身并不表示链表的元素），这样每次执行的结果直接链接到新链表尾部即可。
- 定义尾指针（指向链表的最后一个结点）方便在O(1)时间复杂度上插入新的结点
代码
public class ListNode {
Integer val;
ListNode next;
ListNode(Integer x) { val = x; }
}
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode head = new ListNode(null);//定义头节点，元素值为null
ListNode tail = head;//定义尾指针
int carry = 0;//表示进位
while(l1 != null || l2 != null){//直到两个链表都遍历完全
int num1 = (l1 != null) ? l1.val : 0;//l1如果为null，则加数为0
int num2 = (l2 != null) ? l2.val : 0;//l2如果为null，则加数为0
int res = num1 + num2 + carry;//两数相加，需要同时加进位carry
ListNode node = new ListNode(res % 10);//余数为当前结点加和的结果
tail.next = node;//链接到尾结点之后
tail = node;//尾引用指向新的尾结点
carry = res / 10;//求进位值
if(l1 != null){//不为null继续遍历
l1 = l1.next;
}
if(l2 != null){//不为null继续遍历
l2 = l2.next;
}
}
if(carry > 0){//遍历结束，如果进位大于0，新结点保存
ListNode node = new ListNode(carry);
tail.next = node;
}
return head.next;//返回链表的第一个结点
}
