#yyds干货盘点# 面试必刷TOP101：链表相加(二)

1.简述：

描述

假设链表中每一个节点的值都在 0 - 9 之间，那么链表整体就可以代表一个整数。

给定两个这种链表，请生成代表两个整数相加值的结果链表。

数据范围：，链表任意值 要求：空间复杂度 ，时间复杂度 

例如：链表 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}

2.代码实现：

import java.util.*;

/*
* public class ListNode {
* int val;
* ListNode next = null;
* }
*/

public class Solution {
/**
*
* @param head1 ListNode类
* @param head2 ListNode类
* @return ListNode类
*/
public ListNode addInList (ListNode head1, ListNode head2) {
// 进行判空处理
if(head1 == null)
return head2;
if(head2 == null){
return head1;
}
// 反转h1链表
head1 = reverse(head1);
// 反转h2链表
head2 = reverse(head2);
// 创建新的链表头节点
ListNode head = new ListNode(-1);
ListNode nHead = head;
// 记录进位的数值
int tmp = 0;
while(head1 != null || head2 != null){
// val用来累加此时的数值（加数+加数+上一位的进位=当前总的数值）
int val = tmp;
// 当节点不为空的时候，则需要加上当前节点的值
if (head1 != null) {
val += head1.val;
head1 = head1.next;
}
// 当节点不为空的时候，则需要加上当前节点的值
if (head2 != null) {
val += head2.val;
head2 = head2.next;
}
// 求出进位
tmp = val/10;
// 进位后剩下的数值即为当前节点的数值
nHead.next = new ListNode(val%10);
// 下一个节点
nHead = nHead.next;

}
// 最后当两条链表都加完的时候，进位不为0的时候，则需要再加上这个进位
if(tmp > 0){
nHead.next = new ListNode(tmp);
}
// 重新反转回来返回
return reverse(head.next);
}

// 反转链表
ListNode reverse(ListNode head){
if(head == null)
return head;
ListNode cur = head;
ListNode node = null;
while(cur != null){
ListNode tail = cur.next;
cur.next = node;
node = cur;
cur = tail;
}
return node;
}
}