力扣：两数相加

一、问题描述

二、解题路线

   第一次看到这题，一开始的思路是，调用函数addTwoNumbers(l1,  l2)，传入函数两个链表。然后分别计算每个链表对应的数值（比如：2->3->1，对应数值是342），之后求出两个数值的和sum，最后通过while循环对sum取余和除10取整的操作再把各个位的数添加到一个链表中，最后返回链表。 

   但是没通过，发现了问题，题中要求是链表各个节点存储一位，节点个数是在[1,100]范围内。例如，如果节点个数是20，或者更多，那就超过了int或long能表示的范围，所以最开始的思路不可取，放弃。

  然后第二个思路，从两个链表最低位（链表头）开始，向最高位（链表尾）遍历，将两个链表对应位相加，如果有进位，则保留进位，加到下一次循环。这样每一次循环都可以计算出对应链表的节点值以及是否需要向高位进位。

  最后有一个注意点：当两个链表链表尾（最高位）执行相加操作（如果有一个链表遍历完毕，就遍历另一个知道都遍历完毕）时候，如果有进位怎么办？ 我的做法是设立一个标志flag，每一次循环都跟踪对应结点数值相加（有进位把进位也加进去）的和，如果大于10，那么表示如果当前位数是链表尾（最高位），需要向高位进位1。如果不是，那么不用修改flag的值，同时设置进位为0。最后进行一次判断，是否将进位加入到链表。

三、参考答案

代码如下：

package demo1;

import java.util.Scanner;

public class AddTwoNumbers {
	
	public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
		ListNode l = null, tail = null;
		int more = 0;//进位
		int sum;//两个数，对应位相加和
		int flag = 0;//最高位，判断是否进位 flag为1 进位
		int nodeVal = 0;//节点值
		while(l1 != null || l2 != null) {
			flag = 0;
			if(l1 != null && l2 != null) {
				sum = l1.val + l2.val + more;	
				if(l1.val + l2.val + more > 9) flag = 1;//当前对应位数相加应当进位 设置flag=1；
				else more = 0;//无进位设置more=0
				l1 = l1.next;
				l2 = l2.next;
			} else if(l1 == null && l2 != null) {
				sum = l2.val + more;
				if(l2.val + more > 9) flag = 1;
				else more = 0;
				l2 = l2.next;
			} else {
				sum = l1.val + more;
				if(l1.val + more > 9) flag = 1;
				else more = 0;
				l1 = l1.next;
			}
			nodeVal = sum;
			if(sum > 9) {
				more = 1;//进位
				nodeVal = sum-10;//存在节点的值
			}
			if(l == null) {
				l = tail = new ListNode(nodeVal);
			} else {
				tail.next = new ListNode(nodeVal);
				tail = tail.next;//链表增加节点
			}	
		}
		if(more != 0 && flag == 1) {//判断 如果最高位有进位，也添加至链表
			if(l == null) {
				l = tail = new ListNode(more);
			} else {
				tail.next = new ListNode(more);
				tail = tail.next;
			}
			
		}
        return l;
    }
	
	public static ListNode createLinkedByArray(int[] nums) {//通过数组创建链表
		ListNode head = null, tail = null;
		for(int i = 0; i < nums.length; i++) {
			if(head == null) {
				head = tail = new ListNode(nums[i]);
			} else {
				tail.next = new ListNode(nums[i]);
				tail = tail.next;
			}
		}
		tail.next = null;
		return head;
	}
	
	public static void main(String[] args) {
		AddTwoNumbers a = new AddTwoNumbers();
		Scanner sc = new Scanner(System.in);
		//定义两个数组
		int arr1[] = new int[3];
		int arr2[] = new int[3];
		ListNode l1;
		ListNode l2;
		ListNode l = new ListNode();
		System.out.println("输入数组1：");
		for(int i = 0; i < arr1.length; i++) {
			arr1[i] = sc.nextInt();
		}
		System.out.println("输入数组2：");
		for(int i = 0; i < arr2.length; i++) {
			arr2[i] = sc.nextInt();
		}
		l1 = createLinkedByArray(arr1);
		l2 = createLinkedByArray(arr2);
		l1.print();
		System.out.println();
		l2.print();
		System.out.println();
		l = a.addTwoNumbers(l1, l2);
		l.print();
	}
}