0%

leetCode-2:Add Two Numbers

问题描述

给定两个链表,链表中的数字是非负整数,表示一个整数的逆序,要求将这两个链表进行相加。其实就是模拟大数相加的过程。题目链接:**点我**

样例输入输出

输入: (2 -> 4 -> 3) (5 -> 6 -> 4)

输出: (7 -> 0 -> 8)

输入: (1) (9 -> 9 -> 2)

输出: (0 -> 0 -> 3)

问题解法

直接模拟相加

遍历链表,对遍历过的节点的值进行相加,再与前一个节点产生的进位进行相加,再将结果模10得到本新节点的值,将和除10得到新的进位与下个节点进行相加。代码实现如下

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
58
59
60
61
62
63
64
65
66
67
68
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution
{
private void handleRemainList(ListNode resultCurrent, ListNode p, int prevCarryNum)
{
while (prevCarryNum > 0)
{
int sum = prevCarryNum;
if (p != null)
{
sum += p.val;
p = p.next;
}
resultCurrent.next = new ListNode(sum % 10);
resultCurrent = resultCurrent.next;
prevCarryNum = sum / 10;
}
resultCurrent.next = p;
}

public ListNode addTwoNumbers(ListNode l1, ListNode l2)
{
if (l1 == null)
{
return l2;
}

if (l2 == null)
{
return l1;
}

ListNode p1 = l1;
ListNode p2 = l2;
ListNode result = new ListNode((p1.val + p2.val) % 10);
ListNode resultCurrent = result;
int prevCarryNum = (p1.val + p2.val) / 10;
p1 = p1.next;
p2 = p2.next;
while (p1 != null && p2 != null)
{
int sum = p1.val + p2.val + prevCarryNum;
resultCurrent.next = new ListNode(sum % 10);
prevCarryNum = sum / 10;
resultCurrent = resultCurrent.next;
p1 = p1.next;
p2 = p2.next;
}

if (p1 == null)
{
handleRemainList(resultCurrent, p2, prevCarryNum);
}
else
{
handleRemainList(resultCurrent, p1, prevCarryNum);
}

return result;
}
}

以上代码主要是同时遍历链表,遇到一个链表为空时,处理剩下的链表,代码有点啰嗦,leetcode上有更简便的写法,请参考**这里**

使用BigInteger

本题是模拟两个大数相加的过程,在java库中已经有BigInteger类实现了大数相加、相减、相乘、相除等功能,因此可以直接使用这个类来完成本题。代码如下

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
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
import java.math.BigInteger;
class Solution
{
private String getStringNumber(ListNode p)
{
StringBuilder sb = new StringBuilder();
while (p != null)
{
sb.append(p.val);
p = p.next;
}

return sb.reverse().toString();
}

public ListNode addTwoNumbers(ListNode l1, ListNode l2)
{
if (l1 == null)
{
return l2;
}

if (l2 == null)
{
return l1;
}

String firstNum = getStringNumber(l1);
String secondNum = getStringNumber(l2);

BigInteger firstBigNum = new BigInteger(firstNum);
BigInteger secondBigNum = new BigInteger(secondNum);

String sumString = firstBigNum.add(secondBigNum).toString();
StringBuilder sb = new StringBuilder(sumString).reverse();
ListNode result = new ListNode(Integer.valueOf(Character.toString(sb.charAt(0))));
ListNode current = result;
for (int i = 1; i < sb.length(); i++)
{
current.next = new ListNode(Integer.valueOf(Character.toString(sb.charAt(i))));
current = current.next;
}
return result;
}
}

由于传入的参数是链表,且是逆序的数字,因此需要先将其转出正序整数的字符串,然后使用BigInteger.add进行相加。最后再将结果转出逆序的整数字符串,再构造链表返回。由于此过程涉及转换比较多,因此效率低下,不如第一种效率好。但是当传入参数为字符串并且要求返回的参数为字符串时,此种方法不比第一种差,且可读性较好。