求和两个链表

Question

我有一个这样的节点：

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) {}
};

我想用递归求和两个链表。我不确定，但我想这是尾部递归。

输入：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";

我看不出哪里出了问题，它应该起作用。我错过了什么？

Answer 1

有几个问题：

• 您的递归从未停止，这就是分段错误的原因——在递归调用中，您计算l1->next，但在某个点上，l1将是一个空指针，因此您会得到异常。所谓的"；基本情况"；缺少的递归。当两个列表指针都为null并且没有进位时，不应该进行递归调用，而应该返回null指针
• (n1 + n2 + carry) - 10是错误的公式。它应该是(n1 + n2 + carry) / 10
• result = result->next;是错误的，因为您将永远失去对刚刚创建的节点的引用。一旦创建了新列表的标题，该标题就不需要再次更改。当您首先将参数的头值加在一起时，结果中的和也应该是第一个，对第一个节点的引用是函数应该返回的

还有：

• 不需要将result作为参数传递。确保递归调用为作为参数传递的较短列表返回一致的结果(链表(。然后；仅"；您所要做的就是将当前和作为返回列表的一个节点，然后就完成了。因此，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));
}