求和两个链表
Sum two Linked Lists
我有这样一个节点:
struct ListNode {
int val;
ListNode *next;
ListNode()
: val(0), next(nullptr) {}
ListNode(int x)
: val(x), next(nullptr) {}
ListNode(int x, ListNode *next)
: val(x), next(next) {}
};
我想使用递归对两个 link 列表求和。我不确定,但我猜是尾递归。
输入: l1 = [2,4,3], l2 = [5,6,4]
输出: [7,0,8]
解释:342 + 465 = 807。
这是我的代码:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2, int carry = 0,ListNode *result = nullptr) {
int n1 = l1 != nullptr ? l1->val : 0;
int n2 = l2 != nullptr ? l2->val : 0;
int val = (n1 + n2 + carry) % 10;
if(result == nullptr){
result = new ListNode(val);
}else{
result->next = new ListNode(val);
result = result->next;
}
result = addTwoNumbers(l1->next != nullptr ? l1->next : nullptr,
l2->next != nullptr ? l2->next : nullptr,
(n1 + n2 + carry) - 10,result);
return result;
}
但是我遇到了分段错误,即使在传递两个单节点列表时也是如此:
ListNode * a = new ListNode(1);
ListNode * b = new ListNode(2);
ListNode * c = addTwoNumbers(a, b);
std::cout << c->val << "\n";
我看不出有什么问题,应该可以。我错过了什么?
有几个问题:
- 你的递归永远不会停止,这就是分段错误的原因——在递归调用中你计算
l1->next
,但在某个点 l1
将是一个空指针,所以你得到例外。缺少递归的所谓“基本情况”。当两个列表指针都为空且没有进位时,不应该进行递归调用,而是空指针应该 returned
(n1 + n2 + carry) - 10
是错误的公式。应该是 (n1 + n2 + carry) / 10
.
result = result->next;
是错误的,因为您将永远失去对刚刚创建的节点的引用。一旦您创建了新列表的头部,该头部就不需要再次更改。当您 first 将参数的头部值加在一起时,该总和也应该在结果中 first ,并且对第一个节点的引用是函数应该是什么 return.
还有:
- 应该没有必要将
result
作为参数传递。确保递归调用 return 是作为参数传递的较短列表的一致结果(链接列表)。然后,您需要做的“唯一”事情就是 将当前总和作为节点添加到 returned 列表中,然后就完成了。所以 result
参数真的不需要。
这是更正后的代码:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2, int carry = 0) {
// base case
if (l1 == nullptr && l2 == nullptr && carry == 0) return nullptr;
int n1 = l1 != nullptr ? l1->val : 0;
int n2 = l2 != nullptr ? l2->val : 0;
int sum = n1 + n2 + carry;
return new ListNode(sum % 10,
addTwoNumbers(l1 != nullptr ? l1->next : nullptr,
l2 != nullptr ? l2->next : nullptr, sum / 10));
}
我有这样一个节点:
struct ListNode {
int val;
ListNode *next;
ListNode()
: val(0), next(nullptr) {}
ListNode(int x)
: val(x), next(nullptr) {}
ListNode(int x, ListNode *next)
: val(x), next(next) {}
};
我想使用递归对两个 link 列表求和。我不确定,但我猜是尾递归。
输入: l1 = [2,4,3], l2 = [5,6,4]
输出: [7,0,8]
解释:342 + 465 = 807。
这是我的代码:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2, int carry = 0,ListNode *result = nullptr) {
int n1 = l1 != nullptr ? l1->val : 0;
int n2 = l2 != nullptr ? l2->val : 0;
int val = (n1 + n2 + carry) % 10;
if(result == nullptr){
result = new ListNode(val);
}else{
result->next = new ListNode(val);
result = result->next;
}
result = addTwoNumbers(l1->next != nullptr ? l1->next : nullptr,
l2->next != nullptr ? l2->next : nullptr,
(n1 + n2 + carry) - 10,result);
return result;
}
但是我遇到了分段错误,即使在传递两个单节点列表时也是如此:
ListNode * a = new ListNode(1);
ListNode * b = new ListNode(2);
ListNode * c = addTwoNumbers(a, b);
std::cout << c->val << "\n";
我看不出有什么问题,应该可以。我错过了什么?
有几个问题:
- 你的递归永远不会停止,这就是分段错误的原因——在递归调用中你计算
l1->next
,但在某个点l1
将是一个空指针,所以你得到例外。缺少递归的所谓“基本情况”。当两个列表指针都为空且没有进位时,不应该进行递归调用,而是空指针应该 returned (n1 + n2 + carry) - 10
是错误的公式。应该是(n1 + n2 + carry) / 10
.result = result->next;
是错误的,因为您将永远失去对刚刚创建的节点的引用。一旦您创建了新列表的头部,该头部就不需要再次更改。当您 first 将参数的头部值加在一起时,该总和也应该在结果中 first ,并且对第一个节点的引用是函数应该是什么 return.
还有:
- 应该没有必要将
result
作为参数传递。确保递归调用 return 是作为参数传递的较短列表的一致结果(链接列表)。然后,您需要做的“唯一”事情就是 将当前总和作为节点添加到 returned 列表中,然后就完成了。所以result
参数真的不需要。
这是更正后的代码:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2, int carry = 0) {
// base case
if (l1 == nullptr && l2 == nullptr && carry == 0) return nullptr;
int n1 = l1 != nullptr ? l1->val : 0;
int n2 = l2 != nullptr ? l2->val : 0;
int sum = n1 + n2 + carry;
return new ListNode(sum % 10,
addTwoNumbers(l1 != nullptr ? l1->next : nullptr,
l2 != nullptr ? l2->next : nullptr, sum / 10));
}