20170311804232017-03-12.jpg

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

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

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
* 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) {
}
}

题目是说给你两个存放正整数的链表,链表是倒序放的。让你将两个链表相加,然后返回。

链表

既然是说链表,那来复习一下Java链表的使用。Java中LinkedList表示链表,链表是什么结构就不提了。

LinkedList提到,双向列表实现了列表和队列接口,支持所有列表和队列的操作。并且其不是线程安全的。如果多个线程对链表进行操作,最好使用

1
List list = Collections.synchronizedList(new LinkedList(...));

还有不能同时对链表进行插入和移除操作。刚学那会就犯过这样的错误。

支持任何位置插入,获取,遍历,移除。想了解的自己去看api,但是Linkedlist不适合随意的获取数据。适合对数据的插入,移动等等。我们来个例子。

案例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public void func(){
LinkedList<Integer> list = new LinkedList<>();
list.add(1);
list.add(1,2);
list.addFirst(0);
list.addLast(3);
list.offer(4);
list.offerFirst(-1);
list.offerLast(5);
System.out.println(list.element());
System.out.println(list.getFirst());
System.out.println(list.getLast());
// 还是出队
System.out.println(list.peek());
System.out.println(list.peekFirst());
System.out.println(list.peekLast());
System.out.println(list.pop());
list.push(5);
System.out.println(list.peekLast());
}

结果是这样的:

2017031136465Screen Shot 2017-03-11 at 11.17.42 PM.png

从上面可以看出LinkedList可以作为栈,队列使用。

解决方案一

题目中要求只能使用自定义链表的形式来做,而且从结构上看只能使用单链表。上面的内容就当复习链表的特性吧。也可以查看维基百科

分析

  • 首先,链表是反序的。所以我们需要将链表反序输出,正好符合栈的先进后出原则。
  • 如果两个栈的长度不相同,那么弹出栈中的数据时,会报告异常,那么我们将长度不够的栈后面添加0,使得两个栈长度相同。
  • 现在两个栈长度相同了,但是两个数相加超过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
69
70
71
72
73
74
75
/**
* 自己的解法
* @param l1
* @param l2
* @return
*/
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode node = new ListNode(0);
ListNode temp;
ListNode curl = new ListNode(0);
Stack<Integer> stack1 = reverseListNode(l1);
Stack<Integer> stack2 = reverseListNode(l2);
int size = Math.abs(stack1.size() - stack2.size());
if (stack1.size() > stack2.size()) {
pushZero(stack2, size);
} else {
pushZero(stack1, size);
}
int i = 0;
int j = 0;
boolean flag = false;
while (!stack1.isEmpty() && j < stack1.size()) {
int data = stack1.get(j) + stack2.get(j);
if (flag) {
data += 1;
flag = false;
}
if (data >= 10) {
temp = new ListNode(data % 10);
flag = true;
} else {
temp = new ListNode(data);
}
if (i == 0) {
node = temp;
} else {
curl.next = temp;
}
curl = temp;
i++;
j++;
// 如果最后计算的数仍然需要进位,那么在链表后面+1
if (flag&&j==stack1.size()) {
curl.next = new ListNode(1);
break;
}
}
return node;
}
/**
* 比较两个链表,对于长度不够的位置置空
* @param stack
* @param size
*/
public void pushZero(Stack<Integer> stack, int size) {
for (int i = 0; i < size; i++) {
stack.push(0);
}
}
/**
* 反转链表为栈
* @param node
* @return
*/
public Stack<Integer> reverseListNode(ListNode node) {
Stack stack = new Stack();
ListNode listNode = node;
while (listNode != null) {
stack.push(listNode.val);
listNode = listNode.next;
}
return stack;
}

从上面的代码看来,我们进行了四次循环操作,时间复杂度位O(4*n)

解决方案二

分析

这种方式是在leetcode上看到的标准解答方法。

其实,链表是反的,所以我们的第一思路是将表加入到栈中,然后进行运行。比如两个链表是这样:

1 2 3 4
9 9 7 8

然后我们要运算,那么就需要讲链表反过来,加入堆栈如下:

4 3 2 1
8 7 9 9

但是其实,我们反序后,每个数字的相加是没有变的,比如9+1,8+4。只是计算方向变了,而堆栈取的顺序就是后进先出,而链表是从第一个开始遍历的。所以第一个算法我们多做了一些操作。

实例代码

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
/**
* 网上最优的解法
* @param l1
* @param l2
* @return
*/
public ListNode addTwoNumbers1(ListNode l1, ListNode l2) {
ListNode prev = new ListNode(0);
ListNode head = prev;
// 判断是否进位
int carry = 0;
while (l1 != null || l2 != null || carry != 0) {
ListNode cur = new ListNode(0);
// 求和
int sum = ((l2 == null) ? 0 : l2.val) + ((l1 == null) ? 0 : l1.val) + carry;
// 得到当前位的结果
cur.val = sum % 10;
// 得到当前位的进位
carry = sum / 10;
// 指定prev的下个节点位cur
prev.next = cur;
// 将pre节点移动到cur
prev = cur;
// 根据l1,l2是否有值进行移动
l1 = (l1 == null) ? l1 : l1.next;
l2 = (l2 == null) ? l2 : l2.next;
}
return head.next;
}

这种方式相比前面那个,看出了整个运算的本质。时间复杂度也好上不少。

拓展

单链表的倒叙输出

将链表节点遍历,然后放入栈中,将栈输出:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
* 反转链表为栈
* @param node
* @return
*/
public Stack<Integer> reverseListNode(ListNode node) {
Stack stack = new Stack();
ListNode listNode = node;
while (listNode != null) {
stack.push(listNode.val);
listNode = listNode.next;
}
return stack;
}

查到单链表倒数第k个元素

获取单链表的中间元素

两个有序单链表合并

判断两个单链表是否相交

获取两个单链表相交的结点

判断单链表是否有环

判断有环单链表中,环的长度

获取单链表中,环的起始结点

删除单链表中指定结点