两数相加

题目

两个非空的链表逆序表示两个非负的整数，每个节点只存储一位数字，例如：数组567表示为7->6->5。求两数相加的和，结果返回一个新链表逆序表示。

示例：
输入：1->2->3 和 7->5->2
输出：8->7->5
原因：321+257=578

知识点

这道题目用到了除法，取余，进位，头指针，空处理等知识点。

除法和取余

System.out.println("Integer---213");
System.out.println(213%10);
System.out.println(213/10);

System.out.println("Integer---MAX_VALUE---"+Integer.MAX_VALUE);
System.out.println(Integer.MAX_VALUE%10);
System.out.println(Integer.MAX_VALUE/10);

System.out.println("Integer---MIN_VALUE---"+Integer.MIN_VALUE);
System.out.println(Integer.MIN_VALUE%10);
System.out.println(Integer.MIN_VALUE/10);

输出

Integer---213
3
21
Integer---MAX_VALUE---2147483647
7
214748364
Integer---MIN_VALUE----2147483648
-8
-214748364

进位

• 进位 carry 必定是 0 或 1，这是因为两个数字相加（考虑到进位）可能出现的最大和为 9 + 9 + 1 =19。
• 求和运算最后可能出现额外的进位，这一点很容易被遗忘

	    if (carry > 0) {//遍历结束，如果进位大于0，新结点保存
	        curr.next = new ListNode(carry);
	    }

头指针

设置一个头指针ListNode dummyHead = new ListNode(0);最后返回时，返回dummyHead.next。

空处理

两个链表相加时，要考虑一个比较长，或者为空的情况。代码中采用三元表达式来操作int x = (p != null) ? p.val : 0;和int y = (q != null) ? q.val : 0;

ListNode

package add_two_numbers;

public class ListNode {

	int val;
	ListNode next;
	ListNode(int x){val = x;}
	
	@Override
	public String toString() {
		ListNode ss = this;
		while(ss!=null) {
			String ssss = ss.next==null?"":"->";
			System.out.print(ss.val+ssss);
			ss = ss.next;
		}
		System.out.println();
		return super.toString();
	}
}

Solution

package add_two_numbers;

public class Solution {

	/**add-two-numbers*/
	public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
	    ListNode dummyHead = new ListNode(0);
	    //三个指针，指向当前计算的位数
	    ListNode p = l1, q = l2, curr = dummyHead;
	    int carry = 0;
	    while (p != null || q != null) {
	        int x = (p != null) ? p.val : 0;
	        int y = (q != null) ? q.val : 0;
	        //进位
	        int sum = carry + x + y;
	        //计算进位
	        carry = sum / 10;
	        //取余
	        curr.next = new ListNode(sum % 10);
	        curr = curr.next;
	        if (p != null) p = p.next;
	        if (q != null) q = q.next;
	    }
	    if (carry > 0) {//遍历结束，如果进位大于0，新结点保存
	        curr.next = new ListNode(carry);
	    }
	    return dummyHead.next;//返回链表的第一个结点
	}
	
	public static void main(String[] args) {
		ListNode l1 = new ListNode(1);
		ListNode l1_2 = new ListNode(2);
		ListNode l1_3 = new ListNode(3);
		l1.next = l1_2;
		l1_2.next = l1_3;
		l1.toString();
		
		ListNode l2 = new ListNode(7);
		l2.next = new ListNode(5);
		l2.next.next = new ListNode(2);
		l2.toString();
		
		Solution solu = new Solution();
		ListNode l3 = solu.addTwoNumbers(l1,l2);
		l3.toString();
	}

}

输出

1->2->3
7->5->2
8->7->5

参考资料

两数相加_详解
两数相加（add-two-numbers）
两数相加ii（add-two-numbers-ii）