嘿,我刚刚在学校参加了一个测验,其中涉及到C ++链表,但我想不通如何以教授想要的方式使用该功能。测验已经结束,但是我还是想解决它,并尝试更好地理解链表。我已经尝试了3个小时来解决这个问题,因此,不胜感激。
odd_even需要具有此签名,并且必须是递归解决方案。h是传入的原始链表,节点分为奇数和偶数列表。完成拆分后,奇数和偶数最初设置为nullptr,奇数偶数将原始列表h设置为nullptr。他还说,这将是一个解构性的解决方案,不要创建新的列表或节点。我对此不是100%清楚,但我认为它仅应操作/重新分配现有节点。
我已经尝试了很多事情,但这就是我提交的内容:
node* odd_even(node* p, node*& odd, node*& even) {
if (!p) {
return nullptr;
}
else if (p->data % 2 == 0) {
even = p;
even->next = odd_even(p->next, odd, even->next);
}
else {
odd = p;
odd->next = odd_even(p->next, odd->next, even);
}
return p;
}
int main() {
node* odd = nullptr;
node* even = nullptr;
node* h = new node{ 1, new node{3, new node{5, new node{6, new node{8, new node{9, nullptr} } } } } };
printr(h);
h = odd_even(h, odd, even);
printr(h);
printr(odd);
printr(even);
}
Expected Input:
node* h: 1->3->5->6->8->9->nullptr
node* odd, even: nullptr.
Expected Output:
h: 1->3->5->6->8->9->nullptr
h = odd_even(h, odd, even)
h: nullptr
even: 6->8->nullptr
odd: 1->3->5->9->nullptr
我尝试通过尾部递归调用为每个列表找到下一个节点,但是当它从奇数调用转换为偶数调用时(反之亦然),该节点将崩溃。我尝试了递归调用,直到列表的末尾,然后将它们拆分回去,但是随后抓住第一个节点很困难,我也不认为这是解决方案。我也遇到了使整个事情最终返回nullptr的问题……我只是认为我没有正确地使用它,因此我可以在这里使用一些指导。谢谢!
更新:我花了几个小时在上面,并提出了两种解决方案。1比另一个确定的要好。感谢您的反馈,我很高兴自己先自己弄清楚了。我期待阅读评论,我敢肯定有比我更好的方法了。
我的第一个解决方案(简洁但最后不为原始列表返回nullptr……):
node* odd_even(node* p, node*& odd, node*& even) {
if (!p) {
return nullptr;
}
p->next = odd_even(p->next, odd, even);
if (p->data % 2 == 0 ) {
p->next = even;
even = p;
}else {
p->next = odd;
odd = p;
}
return p;
}
我的第二个解决方案(有点混乱,但满足了所有要求):
node* odd_even(node* p, node*& odd, node*& even) {
if (!p) {
return nullptr;
}
if (p->data % 2 == 0) {
even = p;
}else {
odd = p;
}
if (p->next) {
if (p->next->data % 2 == 0) {
if (even) {
even->next = odd_even(p->next, odd, even->next);
}else {
even = odd_even(p->next, odd, even);
}
}else {
if (odd) {
odd->next = odd_even(p->next, odd->next, even);
}else {
odd = odd_even(p->next, odd, even);
}
}
return p;
}
even->next = odd_even(p->next, odd, even);
odd->next = odd_even(p->next, odd, even);
}
odd_even()
通过重新连接一个旧列表创建了两个新列表。
到现在为止还挺好。
不幸的是,当您将旧列表中的所有节点都放置在它们所属的位置时,您忘记了通过将最终的下一个指针设置为null来终止它们。因此,一个将具有原始的最后一个节点并因此终止,而另一个从另一个列表链接到某个节点。
您在哪里终止?好吧,就在返回null之前。
另外,您应该直接返回null或通过tail递归返回。
node* odd_even(node* p, node*& odd, node*& even) noexcept {
if (!p) {
odd = even = nullptr;
return nullptr;
} else if (p->data % 2) {
odd = p;
return odd_even(p->next, p->next, even);
} else {
even = p;
return odd_even(p->next, odd, p->next);
}
}
顺便说一下,这是一个糟糕的递归演示,因为迭代版本更简单,并且不依赖编译器来消除递归调用,这在此处应视实现的质量而定。
node* odd_even(node* p, node*& odd, node*& even) noexcept {
auto p_odd = &odd, p_even = &even;
for (; p; p = p->next) {
auto& chosen = p->data % 2 ? p_odd : p_even;
*chosen = p;
chosen = &p->next;
}
*p_odd = *p_even = nullptr;
return nullptr;
}
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句