你有两个用链表代表的整数,其中每个节点包含一个数字。数字存储按照在原来整数中相反
的顺序,使得第一个数字位于链表的开头。写出一个函数将两个整数相加,用链表形式返回和。
给出两个链表 3->1->4->null
和 5->9->2->null
,返回 8->0->7->null
。
其实就是
413 + 295 = 708
数字全部以相反的顺序存储。
首先依次取链表的元素,第一次取的就是最低位,个位,第二次就是十位,以此类推。
正好此顺序是正常加法运算的顺序,所以将每一位计算完后的数对10取余,就是 保留数
,对10整除就是 进位数
。
如:5 + 9 = 14
那么, 14 % 10 = 4
14 / 10 = 1
。
所以每次将 保留数
存储下来,然后下一位的运算加上 进位数
即可,依次类推。最终计算出结果。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
/**
* @param l1: the first list
* @param l2: the second list
* @return: the sum list of l1 and l2
*/
public ListNode addLists(ListNode l1, ListNode l2) {
if(l1 == null && l2 == null) {
return null;
}
ListNode head = new ListNode(0);
ListNode point = head;
int carry = 0;
while(l1 != null && l2!=null){
int sum = carry + l1.val + l2.val;
point.next = new ListNode(sum % 10);
carry = sum / 10;
l1 = l1.next;
l2 = l2.next;
point = point.next;
}
while(l1 != null) {
int sum = carry + l1.val;
point.next = new ListNode(sum % 10);
carry = sum /10;
l1 = l1.next;
point = point.next;
}
while(l2 != null) {
int sum = carry + l2.val;
point.next = new ListNode(sum % 10);
carry = sum /10;
l2 = l2.next;
point = point.next;
}
if (carry != 0) {
point.next = new ListNode(carry);
}
return head.next;
}
}