AddTwoNumbersII [source code]
public class AddTwoNumbersII {
static
/******************************************************************************/
class Solution {
int carry = 0;
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
if (l1 == null)
return l2;
if (l2 == null)
return l1;
ListNode res;
int len1 = getLen(l1), len2 = getLen(l2);
if (len1 < len2) {
res = add(l1, l2, len2 - len1);
} else {
res = add(l2, l1, len1 - len2);
}
if (carry > 0) {
ListNode res1 = res;
res = new ListNode(carry);
res.next = res1;
}
return res;
}
public int getLen(ListNode l1) {
int len = 0;
while (l1 != null) {
len++;
l1 = l1.next;
}
return len;
}
//l2.length - l1.length == diff;
public ListNode add(ListNode l1, ListNode l2, int diff) {
if (l1.next == null && l2.next == null) {
int sum = l1.val + l2.val;
carry = sum / 10;
return new ListNode(sum % 10);
}
ListNode res, next;
int sum;
if (diff == 0) {
next = add(l1.next, l2.next, 0);
sum = l1.val + l2.val + carry;
} else {
next = add(l1, l2.next, diff - 1);
sum = carry + l2.val;
}
carry = sum / 10;
res = new ListNode(sum % 10);
res.next = next;
return res;
}
}
/******************************************************************************/
public static void main(String[] args) {
AddTwoNumbersII.Solution tester = new AddTwoNumbersII.Solution();
}
}
这个问题还是一个reverse visit linked list的题型, 第一个想法还是reverse, 可惜Follow-Up里面直接禁用了. 怎么办? (确实, 要是用reverse, 这个题目就是easy了);
刚开始有一个想法, 直接一个recursion一做到底, 但是跑了一个例子(这个题目一定要在纸上配合例子写代码, 不然很容易写乱)之后, 发现这种:
public ListNode add(ListNode l1, ListNode l2) {
if (l1.next == null && l2.next == null) {
int sum = l1.val + l2.val + carry;
carry = sum % 10;
return new ListNode(sum / 10);
}
ListNode res, next;
int sum;
if (l1.next == null && l2.next != null) {
isL1Shorter = true;
next = addTwoNumbers(l1, l2.next);;
sum = carry + l2.val;
} else if (l1.next != null && l2.next == null) {
next = addTwoNumbers(l1.next, l2);
sum = l1.val + carry;
} else {
next = addTwoNumbers(l1.next, l2.next);
if (isL1Shorter) {
sum =
}
}
carry = sum % 10;
res = new ListNode(sum / 10);
}
直接在每一个level同时remove head的做法好像是不对的; 这种做法在比如12+3456的例子当中, 会始终把1和3对位, 但是这个对位在上行的过程中很难处理, 1正确的对位应该是5, 但是这个在recursion的上行过程中就很难处理了;
想了半小时还是没有一个特别好的思路, 决定用笨办法了: 聪明办法感觉就是写一个可以无视length difference的算法, 但是好像很难; 所以只能直接先分别测量长度; furthermore, 我们可以直接pad head of shorter list, 这样最后的reverse visit就非常方便的一个recursion可以解决;
但是这个padding的思路好像有问题, 这个题目说了不能modify, 这个padding虽然不是reverse, 不过其实也算是modify了(modify然后最后退出的时候还原的做法估计也不行, 有些面试官估计还是不会允许);
这个题目写算法的时候, 草稿上始终是思考在:
1 2
3 4 5 6
这样的一个例子当中, recursion的每一个iteration是什么. 比如第一个iteration是(1,3), 然后你应该怎么动? 脑子里要有一个动画跑完这一遍;
能够从这个角度思考, 这个问题就很简单了, 最后的速度是54ms (82%);
注意, 这里我故意设计的这个add函数第二个参数比第一个参数长, 这样diff就可以始终保持是正数, 操作起来方便一些; 但是这个好像不是必要的; diff就算是负数这个函数感觉还是写的起来的: 只不过recursion的body里面除了有diff - 1, 也还有diff - 1的操作? 既然要定义正负号, 那么就要想好这个定义的具体细节, 正号和负号分别对应的是什么? 严格定义的话, 可以说diff = l1.length - l2.length, 所以diff是正数就是l1更长, diff是负数就是l2更长. diff的作用就是在不等于0的时候, 我们只移动一边, 同时对应方向修改diff, 最后(无论是从负数出发还是从正数出发)得到0就行了, 然后开始正经的加法操作;
另外, 我这题想到用recursion做, 除了一方面是避免了modify, 同时做到O(N)时间(这个是显然的要求), 同时还是因为做到了O(1)空间. 如果不是追求这个空间的复杂度, 这题完全可以先把两个list的digit全都用一个Stack装起来, 然后再计算就行了; 不过话说回来, 肯定又有人说recursion的Stack也算额外空间(而且因为深度有限, 还有overflow的风险), 这个东西只能见仁见智了;
这个是discussion上面一个用Stack的解法:
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
int n1 = 0, n2 = 0;
for (ListNode i = l1; i != null; i = i.next) n1++;
for (ListNode i = l2; i != null; i = i.next) n2++;
Stack<Integer> st = new Stack();
int totn = Math.max(n1, n2);
for (ListNode i = l1, j = l2; totn > 0; totn--) {
int a = 0, b = 0;
if (totn <= n1) {
a = i.val;
i = i.next;
}
if (totn <= n2) {
b = j.val;
j = j.next;
}
st.push(a + b);
}
int c = 0;
ListNode ans = null;
while (!st.empty()) {
ListNode i = new ListNode(st.pop());
int c1 = (c + i.val) / 10;
i.val = (c + i.val) % 10;
i.next = ans;
ans = i;
c = c1;
}
if (c > 0) {
ListNode i = new ListNode(c);
i.next = ans;
ans = i;
}
return ans;
}
不同的是, 这个并不是很简单的直接把两个list先分别倒到两个Stack里面, 而是用类似我的分析length difference的方法, 先直接做, 用diff来完成一个对位的操作, 把所有的结果都放到一个Stack里面, 这样就不需要reverse了;
究其原因, 这个问题需要解决的一个难题就是怎么完成这个reverse的过程:
- 你可以直接先把两个operand都reverse, 不过这个方法被Follow-Up给禁止了;
- 你可以把两个operand都分别先倒到两个Stack里面去, 这样就已经完成了一个reverse的过程, 最后做输出结果的时候就不需要reverse了;
- 你可以直接在两个operand现有的顺序上面做(当然, 要处理好对位), 然后最后一个reverse, 这个reverse可以用Stack来完成, 也可以用类似我的recursion来完成;
这个算法跟我的非常相似:
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
int size1 = getLength(l1);
int size2 = getLength(l2);
ListNode head = new ListNode(1);
// Make sure l1.length >= l2.length
head.next = size1 < size2 ? helper(l2, l1, size2 - size1) : helper(l1, l2, size1 - size2);
// Handle the first digit
if (head.next.val > 9) {
head.next.val = head.next.val % 10;
return head;
}
return head.next;
}
// get length of the list
public int getLength(ListNode l) {
int count = 0;
while(l != null) {
l = l.next;
count++;
}
return count;
}
// offset is the difference of length between l1 and l2
public ListNode helper(ListNode l1, ListNode l2, int offset) {
if (l1 == null) return null;
// check whether l1 becomes the same length as l2
ListNode result = offset == 0 ? new ListNode(l1.val + l2.val) : new ListNode(l1.val);
ListNode post = offset == 0 ? helper(l1.next, l2.next, 0) : helper(l1.next, l2, offset - 1);
// handle carry
if (post != null && post.val > 9) {
result.val += 1;
post.val = post.val % 10;
}
// combine nodes
result.next = post;
return result;
}
不过他并没有一个explicit的carry; 直接在sum之后分析是否要加一个dummy head就行了;
回顾一下, 这个题目, 跟前面好像有一个two list intersection的题目, 都有一个共同的特点, 就是依赖于对两个list的length difference的分析; 以后碰到这种不等长list的题目的时候, 或许可以从这个角度考虑;
Problem Description
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:
Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 8 -> 0 -> 7
Difficulty:Medium
Total Accepted:27.4K
Total Submissions:59.6K
Contributor: LeetCode
Companies
microsoft bloomberg
Related Topics
linked list
Similar Questions
Add Two Numbers