链表求和

题意

你有两个用链表代表的整数,其中每个节点包含一个数字。数字存储按照在原来整数中相反的顺序,使得第一个数字位于链表的开头。写出一个函数将两个整数相加,用链表形式返回和。

样例

给出两个链表 3->1->4->null5->9->2->null,返回 8->0->7->null

其实就是 413 + 295 = 708 数字全部以相反的顺序存储。

思路

首先依次取链表的元素,第一次取的就是最低位,个位,第二次就是十位,以此类推。
正好此顺序是正常加法运算的顺序,所以将每一位计算完后的数对10取余,就是 保留数 ,对10整除就是 进位数
如:5 + 9 = 14 那么, 14 % 10 = 4 14 / 10 = 1
所以每次将 保留数 存储下来,然后下一位的运算加上 进位数 即可,依次类推。最终计算出结果。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
/**
* 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;

}
}

图解

链表求和.png-59.8kB

原题地址

LintCode:链表求和

坚持原创技术分享,您的支持将鼓励我继续创作!