描述
假设链表中每一个节点的值都在 0 - 9 之间，那么链表整体就可以代表一个整数。
给定两个这种链表，请生成代表两个整数相加值的结果链表。
数据范围：0≤n,m≤10000000≤n,m≤1000000，链表任意值 0≤val≤90≤val≤9
要求：空间复杂度 O(n)O(n)，时间复杂度 O(n)O(n)
例如：链表 1 为 9->3->7，链表 2 为 6->3，最后生成新的结果链表为 1->0->0->0。
示例1
输入：
[9,3,7],[6,3]
返回值：
{1,0,0,0}
说明：
如题面解释
示例2
输入：
[0],[6,3]
返回值：
{6,3}
思路：
1.先将两个单链表逆序，再相加，然后使用头插法插入结点。注意最后一次有进位，但是已经没有结点的情况，此时要比最长的链表长1
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* public ListNode(int val) {
* this.val = val;
* }
* }
*/
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;
head1 = reverse(head1);
head2 = reverse(head2);
ListNode p = head1, q = head2;
int sum = 0;
ListNode dummy = new ListNode(-1);
dummy.next = null;
while (p != null && q != null) {
int t = (sum + p.val + q.val) % 10;
sum = (sum + p.val + q.val) / 10;
ListNode cur = new ListNode(t);
cur.next = dummy.next;
dummy.next = cur;
p = p.next;
q = q.next;
}
while (p != null) {
int t = (sum + p.val) % 10;
sum = (sum + p.val) / 10;
ListNode cur = new ListNode(t);
cur.next = dummy.next;
dummy.next = cur;
p = p.next;
}
while (q != null) {
int t = (sum + q.val) % 10;
sum = (sum + q.val) / 10;
ListNode cur = new ListNode(t);
cur.next = dummy.next;
dummy.next = cur;
q = q.next;
}
if (sum != 0) {
ListNode cur = new ListNode(sum);
cur.next = dummy.next;
dummy.next = cur;
}
return dummy.next;
}
public ListNode reverse(ListNode root) {
if (root == null) return null;
ListNode pre = new ListNode(-1);
pre.next = null;
ListNode cur = root;
while (cur != null) {
ListNode t = cur;
cur = cur.next;
t.next = pre.next;
pre.next = t;
}
return pre.next;
}
}