题目：
分析：
链表中所给的数中，都是按照逆序排序的，也就是说高位在后面，低位在前面，到时候两数相加涉及到低位向高位进位的问题，可以定义一个进位标识。
实现：
public class TwoNumAdd {
//解题主方法
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode head = null, tail = null; //标记头尾，头部最后用来输出，尾部用来连接其他节点
int carry = 0; //进位标志，初始位0
while (l1 != null || l2 != null) {
//两个节点中，只有还有节点不为空就继续
int x = l1 != null ? l1.val : 0; //因为while循环中，是||的判断，存在为空的情况，l1不为空的话x取l1的val值，为空x就取0
int y = l2 != null ? l2.val : 0; //同上
int addNum = x + y + carry; //计算相同位数节点的和（带有地位的进位标志）
carry = addNum / 10; //取进位标志
if (head == null) {
//第一次head为空
tail = head = new ListNode(addNum % 10);
} else {
tail.next = new ListNode(addNum % 10); //之后用tail来添加新节点
tail = tail.next;
}
if (l1 != null) //如果l1不为空，就取l1的下一个节点
l1 = l1.next;
if (l2 != null) //同上
l2 = l2.next;
}
if (carry == 1) {
//while循环结束后，判断是否最高位计算结果是否有进位，在两位数加法中进位只有1
tail.next = new ListNode(1);
tail = tail.next;
}
return head;
}
public static void main(String[] args) {
int []arr1 = new int[]{
9,9,9,9,9,9,9};
int []arr2 = new int[]{
9,9,9,9};
ListNode l1 = arrToListNode(arr1);
ListNode l2 = arrToListNode(arr2);
ListNode listNode = new TwoNumAdd().addTwoNumbers(l1, l2);
ArrayList<Integer> arr = new ArrayList<>();
listNodeToArr(listNode,arr);
System.out.println(arr);
}
//把数组封装成ListNode
public static ListNode arrToListNode(int []arr){
ListNode head = null,tail = null;
for (int i : arr) {
if(head == null){
head = tail = new ListNode(i);
}else {
tail.next = new ListNode(i);
tail = tail.next;
}
}
return head;
}
//递归把ListNode转换为数组
public static void listNodeToArr(ListNode listNode, ArrayList al){
if(listNode.next!=null){
al.add(listNode.val);
listNode = listNode.next;
listNodeToArr(listNode,al);
}
else{
al.add(listNode.val);
}
}
}
class ListNode {
int val;
ListNode next;
public ListNode(int val) {
this.val = val;
}
}
测试输出结果：
递归实现：
public class TwoNumAdd {
//解题主方法
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
int carry = 0;
int addNum = 0;
ListNode head = null, tail = null;
ListNode listNode = this.addTwoNumbersByRecursion(l1, l2, carry,addNum,head,tail);
return listNode;
}
public ListNode addTwoNumbersByRecursion(ListNode l1 ,ListNode l2 , int carry,int addNum,ListNode head,ListNode tail) {
if (l1 != null || l2 != null) {
int x = l1 != null ? l1.val : 0;
int y = l2 != null ? l2.val : 0;
addNum = x + y + carry;
carry = addNum / 10;
if (head == null) {
tail = head = new ListNode(addNum % 10);
} else {
tail.next = new ListNode(addNum % 10);
tail = tail.next;
}
if (l1 != null)
l1 = l1.next;
if (l2 != null)
l2 = l2.next;
head = addTwoNumbersByRecursion(l1, l2, carry, addNum, head, tail);
return head;
} else {
if (carry == 1) {
tail.next = new ListNode(1);
tail = tail.next;
}
return head;
}
}
public static void main(String[] args) {
int []arr1 = new int[]{
9,9,9,9,9,9,9};
int []arr2 = new int[]{
9,9,9,9};
ListNode l1 = arrToListNode(arr1);
ListNode l2 = arrToListNode(arr2);
ListNode listNode = new TwoNumAdd().addTwoNumbers(l1, l2);
ArrayList<Integer> arr = new ArrayList<>();
listNodeToArr(listNode,arr);
System.out.println(arr);
}
//把数组封装成ListNode
public static ListNode arrToListNode(int []arr){
ListNode head = null,tail = null;
for (int i : arr) {
if(head == null){
head = tail = new ListNode(i);
}else {
tail.next = new ListNode(i);
tail = tail.next;
}
}
return head;
}
//递归把ListNode转换为数组
public static void listNodeToArr(ListNode listNode, ArrayList al){
if(listNode.next!=null){
al.add(listNode.val);
listNode = listNode.next;
listNodeToArr(listNode,al);
}
else{
al.add(listNode.val);
}
}
}
class ListNode {
int val;
ListNode next;
public ListNode(int val) {
this.val = val;
}
}
