数据结构算法之leetcode Add Two Numbers

两个非负整数的列表,每个元素都是一个数字,按照由低位到高位排序,求两个链表中的数相加并已链表的方式返回。

例如:
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

这里貌似没有什么高效算法,对两个链表同时遍历相加,并设置一个标识位用来表示是否需要进位。

代码如下:

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
69
70
71
72
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode result = null;
Stack<ListNode> stack = new Stack<ListNode>();
int flag = 0;
while(l1 != null && l2 != null){
int sum = l1.val + l2.val + flag;
int val = sum - 10;
flag = 0;
if(val >= 0){
flag = 1;
}else{
val = sum;
}
ListNode nt = new ListNode(val);
stack.push(nt);
l1 = l1.next;
l2 = l2.next;
}
while(l1 != null){
int sum = l1.val + flag;
int val = sum - 10;
flag = 0;
if(val >= 0){
flag = 1;
}else{
val = sum;
}
ListNode nt = new ListNode(val);
stack.push(nt);
l1 = l1.next;
}
while(l2 != null){
int sum = l2.val + flag;
int val = sum - 10;
flag = 0;
if(val >= 0){
flag = 1;
}else{
val = sum;
}
ListNode nt = new ListNode(val);
stack.push(nt);
l2 = l2.next;
}
if(flag > 0){
ListNode nt = new ListNode(1);
stack.push(nt);
}
while(!stack.empty()){
ListNode temp = null;
temp = stack.pop();
if(result == null){
temp.next = null;
result = temp;
}else{
temp.next = result;
result = temp;
}
}
return result;
}
}

是不是很长,这里还用到了Stack,用Stack来存放各个链表中的各个ListNode。用Stack主要是为了把各个ListNode按照从后往前的顺序拼成链表。

链表的组建方式有两种,一种是从后往前建立连接,这样只需要一个指针;另一种是按照从前往后建立连接,此时需要两个指针,一个是指向链头的first指针,并且first在后续中不会发生变化,另一个指针是last,last会根据链表的元素向后移动,last始终指向链表的最后一个元素。

下面看下从链表头组建链表的代码:

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
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode first = null;
ListNode last = null;
int flag = 0;
while(l1 != null || l2 != null || flag != 0){
int sum = flag;
if(l1 != null){
sum += l1.val;
}
if(l2 != null){
sum += l2.val;
}
flag = sum / 10;
int val = sum % 10;
ListNode temp = new ListNode(val);
if(first == null){
first = temp;
}
if(last == null){
last = temp;
}else{
last.next = temp;
last = temp;
}
if(l1 != null){
l1 = l1.next;
}
if(l2 != null){
l2 = l2.next;
}
}
return first;
}
}

虽然这里多声明了一个变量指针,但是相较于第一个代码也算是一种优化,这里不需要额外的空间去存储相加之后的各个ListNode。时间复杂度都一样只是空间复杂度为O(1)

读上面代码链表组建中first和last指针的赋值是不是有一种一头雾水的感觉,得仔细读下才能撸明白,下面看下leetcode上面的解答代码,感觉比较清晰。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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) {
curr.next = new ListNode(carry);
}
return dummyHead.next;
}

这里声明了一个val为0的dummyHead,使dummyHead作为链表的头节点,并声明一个移动指针curr也指向该节点,这样在链表创建的过程中不用进行太多的判断,只需移动指针curr即可(这也是链表的一种创建方法,貌似当初学数据结构时教科书就是用这种方法创建链表的)。

您的肯定,是我装逼的最大的动力!