p*u
发帖数: 136 | 1 两个单链表（singly linked list），每一个节点里面一个0-9的数字，输入就相当于
两个大数了。然后返回这两个数的和（一个新list）。这两个输入的list长度相等。
要求是：1. 不用递归。2. 要求算法只遍历两个list一次。
1，算法没想到，在别的地方看到的。
2，第一次写挫了，第二次写用了15分钟，用了15分钟写case调试通过
https://gist.github.com/pdu/8083cd76da5976eac5ac |
f****l
发帖数: 8042 | |
f*******w
发帖数: 1243 | 3 所以一开始指向的是位数最高的？
走一遍的时候把sum存到一个新的list，不考虑进位，然后再走一遍新的list，然后翻
转？ |
B*****g
发帖数: 34098 | 4 走到下一位时存上一位的到新list
【在 f*******w 的大作中提到】
: 所以一开始指向的是位数最高的？
: 走一遍的时候把sum存到一个新的list，不考虑进位，然后再走一遍新的list，然后翻
: 转？
|
f*******w
发帖数: 1243 | 5
不行吧
比如 88888 + 11112
【在 B*****g 的大作中提到】
: 走到下一位时存上一位的到新list
|
g****o
发帖数: 547 | 6 head存高位还是低位
低位的话,leetcode有这题啊
【在 p*u 的大作中提到】
: 两个单链表（singly linked list），每一个节点里面一个0-9的数字，输入就相当于
: 两个大数了。然后返回这两个数的和（一个新list）。这两个输入的list长度相等。
: 要求是：1. 不用递归。2. 要求算法只遍历两个list一次。
: 1，算法没想到，在别的地方看到的。
: 2，第一次写挫了，第二次写用了15分钟，用了15分钟写case调试通过
: https://gist.github.com/pdu/8083cd76da5976eac5ac
|
p*u
发帖数: 136 | 7 题目要求存低位，存高位就太简单了。
关键点是：
1，只遍历一次，不能递归
2，比较容易漏掉corner case
3，白板写有点困难~~
【在 g****o 的大作中提到】
: head存高位还是低位
: 低位的话,leetcode有这题啊
|
z*********8
发帖数: 2070 | 8 head存高位比较难吧 或者说不可能一次遍历就搞定
【在 p*u 的大作中提到】
: 题目要求存低位，存高位就太简单了。
: 关键点是：
: 1，只遍历一次，不能递归
: 2，比较容易漏掉corner case
: 3，白板写有点困难~~
|
B*****g
发帖数: 34098 | 9 有道理，我再想想
【在 f*******w 的大作中提到】
:
: 不行吧
: 比如 88888 + 11112
|
B*****g
发帖数: 34098 | 10 要不，只要是9就不加到新list，count一共多少个9，到第一个，不是9的再决定往上放
10000...还是就放9999...
【在 f*******w 的大作中提到】
:
: 不行吧
: 比如 88888 + 11112
|
|
|
f*******w
发帖数: 1243 | 11
所以最坏的情况需要O(n)额外空间？
我也不知道怎样做毕竟好……
【在 B*****g 的大作中提到】
: 要不，只要是9就不加到新list，count一共多少个9，到第一个，不是9的再决定往上放
: 10000...还是就放9999...
|
d****n
发帖数: 233 | 12 A Java version
public static Node add(Node n1, Node n2) {
Node head = new Node(0);
Node back = head;
Node front = head;
while(n1 != null) {
int v = n1.m_value + n2.m_value;
front.next = new Node(v%10);
if (v > 9) {
back.m_value++;
while(back != front){
back = back.next;
back.m_value = 0;
}
back = front = front.next;
}
else if (v < 9){
back = front = front.next;
}
else
front = front.next;
n1 = n1.next;
n2 = n2.next;
}
return head.m_value != 0? head : head.next;
}
【在 B*****g 的大作中提到】
: 要不，只要是9就不加到新list，count一共多少个9，到第一个，不是9的再决定往上放
: 10000...还是就放9999...
|
p*u
发帖数: 136 | 13 赞，你这样写比较巧妙，比我的版本要好看多了。
指正一个小错误：
while(back != front.next){ //这里改为front.next
back = back.next;
back.m_value = 0;
}
你试试这个例子：
445 + 555 = 1000
但是你的代码结果是：1090
【在 d****n 的大作中提到】
: A Java version
: public static Node add(Node n1, Node n2) {
: Node head = new Node(0);
: Node back = head;
: Node front = head;
: while(n1 != null) {
: int v = n1.m_value + n2.m_value;
: front.next = new Node(v%10);
: if (v > 9) {
: back.m_value++;
|
d****n
发帖数: 233 | 14 试了一下， 好像我是对的。
【在 p*u 的大作中提到】
: 赞，你这样写比较巧妙，比我的版本要好看多了。
: 指正一个小错误：
: while(back != front.next){ //这里改为front.next
: back = back.next;
: back.m_value = 0;
: }
: 你试试这个例子：
: 445 + 555 = 1000
: 但是你的代码结果是：1090
|
p*u
发帖数: 136 | 15 嗯，刚看了下你是对的。不好意思看错了
【在 d****n 的大作中提到】
: 试了一下， 好像我是对的。
|
B*****g
发帖数: 34098 | 16 ??O(1)呀
【在 f*******w 的大作中提到】
:
: 所以最坏的情况需要O(n)额外空间？
: 我也不知道怎样做毕竟好……
|
p*******2
发帖数: 50 | 17 mark
关键是找到每次进位链开始和结束的位置吧？ |
c********w
发帖数: 2438 | 18 双指针
一个curr就指向当前的加的结果
一个before指向“9”之前的listnode
【在 p*******2 的大作中提到】
: mark
: 关键是找到每次进位链开始和结束的位置吧？
|
l****1
发帖数: 33 | 19 貌似这个可以:
S=0
C=0
while (not end) {
if (a + b >= 10) {
curr = a + b - 10;
C += 1
} else {
curr = a + b;
}
S = 10 * S + curr;
C = 10 * C;
}
S = S + C; |
s***e
发帖数: 403 | |
l****1
发帖数: 33 | 21 来个C版本的:
static void add_two(struct list *sum, const struct list *a,
const struct list *b)
{
struct list *n1, *n2;
struct list *curr, *last, *end = sum;
char res;
/* reseve one node for carry bit */
curr = alloc_node();
curr->val = 0;
add_node(sum, curr);
end = curr;
last = curr;
n1 = a->next;
n2 = b->next;
while (n1) {
res = n1->val + n2->val;
if (res >= 10) {
last->val++;
res -= 10;
if (last != end) {
for (last = last->next; last != NULL;
last = last->next)
last->val = 0;
last = end;
}
}
curr = alloc_node();
curr->val = res;
add_node(end, curr);
if (res != 9)
last = curr;
n1 = n1->next;
n2 = n2->next;
end = curr;
}
} |
l*n
发帖数: 529 | 22 只能遍历两个输入list一次，没说不能遍历新list多次。把新list逆序记录，有进位就
处理进位，最后再反转。
【在 p*u 的大作中提到】
: 两个单链表（singly linked list），每一个节点里面一个0-9的数字，输入就相当于
: 两个大数了。然后返回这两个数的和（一个新list）。这两个输入的list长度相等。
: 要求是：1. 不用递归。2. 要求算法只遍历两个list一次。
: 1，算法没想到，在别的地方看到的。
: 2，第一次写挫了，第二次写用了15分钟，用了15分钟写case调试通过
: https://gist.github.com/pdu/8083cd76da5976eac5ac
|
