给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储 一位数字。 请你将两个数相加，并以相同形式返回一个表示和的链表。 你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
输入：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]
提示：
每个链表中的节点数在范围 [1, 100] 内 0 ⇐ Node.val ⇐ 9 题目数据保证列表表示的数字不含前导零
解题思路：
- 我们平时怎么计算两个数的和来着？两个数，低位对齐，从低位数字相加。留下余数，进位值向高位递推。链表相加也是这个思路。
- 恰好，两个链表都是 低位⇒高位形式。将两个链表视为等长，不足的部分看成节点值为0即可。这样，程序处理起来方便。
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(-1), last = dummy;
int temp = 0;
while ((l1 != null) || (l2 != null) || (temp > 0))
{
if (l1 != null)
{ temp += l1.val; l1 = l1.next; }
if (l2 != null)
{ temp += l2.val; l2 = l2.next; }
last.next = new ListNode(temp % 10);
last = last.next;
temp /= 10;
}
return dummy.next;
}
}
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head1 ListNode类
* @param head2 ListNode类
* @return ListNode类
*/
public ListNode addInList (ListNode head1, ListNode head2) {
// write code here
// 进行判空处理
if (head1 == null)
return head2;
if (head2 == null) {
return head1;
}
//先进行链表反转，再相加
ListNode h1 = reverse(head1);
ListNode h2 = reverse(head2);
//存放结果集
ListNode head = new ListNode(-1);
ListNode res = head;
int temp = 0;
while (h1 != null || h2 != null || temp > 0) {
if (h1 != null) {
temp = temp + h1.val;
h1 = h1.next;
}
if (h2 != null) {
temp = temp + h2.val;
h2 = h2.next;
}
res.next = new ListNode(temp % 10);
res = res.next;
temp = temp / 10;
}
return reverse( head.next);
}
public ListNode reverse(ListNode node) {
if (node == null) return node;
ListNode pre = null, next = null;
while (node != null) {
next = node.next;
node.next = pre;
pre = node;
node = next;
}
return pre;
}
}