445 Add Two Numbers II

1. Question

You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first 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.
Follow up: What if you cannot modify the input lists? In other words, reversing the lists is not allowed.
Example:
1
Input: (7 -> 2 -> 4 ->3) + (5 -> 6 -> 4)
2
3
Output: 7 -> 8 -> 0 ->7
Copied!

2. Implementation

1
/**
2
* Definition for singly-linked list.
3
* public class ListNode {
4
* int val;
5
* ListNode next;
6
* ListNode(int x) { val = x; }
7
* }
8
*/
9
class Solution {
10
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
11
ListNode p1 = reverse(l1);
12
ListNode p2 = reverse(l2);
13
14
int sum = 0;
15
ListNode dummy = new ListNode(0);
16
ListNode curNode = dummy;
17
18
while (p1 != null || p2 != null) {
19
if (p1 != null) {
20
sum += p1.val;
21
p1 = p1.next;
22
}
23
24
if (p2 != null) {
25
sum += p2.val;
26
p2 = p2.next;
27
}
28
29
curNode.next = new ListNode(sum % 10);
30
sum /= 10;
31
curNode = curNode.next;
32
}
33
34
if (sum != 0) {
35
curNode.next = new ListNode(sum);
36
}
37
38
return reverse(dummy.next);
39
}
40
41
public ListNode reverse (ListNode head) {
42
ListNode curNode = head, preNode = null, nextNode = null;
43
44
while (curNode != null) {
45
nextNode = curNode.next;
46
curNode.next = preNode;
47
preNode = curNode;
48
curNode = nextNode;
49
}
50
return preNode;
51
}
52
}
Copied!

3. Time & Space Complexity

时间复杂度O(m + n), m是第一个list的长度, n是第二个list的长度,空间复杂度O(1)