如何在C ++中将整数链接列表递归拆分为奇数和偶数列表?

詹姆斯·唐尼

嘿,我刚刚在学校参加了一个测验,其中涉及到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] 删除。

编辑于
0

我来说两句

0条评论
登录后参与评论

相关文章

来自分类Dev

将链接列表分为奇数和偶数时,如何“删除”原始链接列表?

来自分类Dev

如何在Python中将没有空格的字符串拆分为整数列表?

来自分类Dev

在 C# 中将大整数列表拆分为字符串列表的最快方法

来自分类Dev

如何在C#中将列表拆分为多个部分?

来自分类Dev

将数字字符串拆分为偶数和奇数整数列表

来自分类Dev

如何将一个嵌套的整数列表拆分为一个列表

来自分类Dev

如何在 input.txt 文件的输出 txt 文件中创建偶数和奇数列表?在蟒蛇

来自分类Dev

如何区分奇数和偶数之间的列表?

来自分类Dev

如何在JavaScript中将数组拆分为单引号和逗号分隔列表

来自分类Dev

如何在JavaScript中将数组拆分为单引号和逗号分隔列表

来自分类Dev

如何在 Python 中将字符串拆分为列表?

来自分类Dev

如何在Scala中将String转换为整数列表?

来自分类Dev

将整数列表分为偶数和奇数和的交替组

来自分类Dev

如何在Java中将列表字符串列表转换为列表整数列表

来自分类Dev

偶数和奇数列表

来自分类Dev

偶数和奇数列表

来自分类Dev

如何将数组拆分为奇数数组和偶数数组

来自分类Dev

如何递归查找整数列表中的最大元素?

来自分类Dev

如何在C ++中将链接列表结构返回给main?

来自分类Dev

如何将整数数组划分为偶数和奇数?

来自分类Dev

给定条件奇数或偶数,如何对列表中的偶数或奇数求和?

来自分类Dev

如何在python中将两个奇数列表添加到一个列表中?

来自分类Dev

如何在Prolog中判断列表长度是奇数还是偶数

来自分类Dev

如何在vb.net中将字符串拆分为列表/数组

来自分类Dev

如何在SQL中将字符串拆分为列表以进行过滤?

来自分类Dev

我如何在Java中将Shapes的ArrayList拆分为分区/列表(仅建议)

来自分类Dev

如何在Python中将列表拆分为不同的字符串

来自分类Dev

如何在python中将列表项换行符拆分为逗号

来自分类Dev

如何在Haskell中将整数列表转换为真与假矩阵

Related 相关文章

  1. 1

    将链接列表分为奇数和偶数时,如何“删除”原始链接列表?

  2. 2

    如何在Python中将没有空格的字符串拆分为整数列表?

  3. 3

    在 C# 中将大整数列表拆分为字符串列表的最快方法

  4. 4

    如何在C#中将列表拆分为多个部分?

  5. 5

    将数字字符串拆分为偶数和奇数整数列表

  6. 6

    如何将一个嵌套的整数列表拆分为一个列表

  7. 7

    如何在 input.txt 文件的输出 txt 文件中创建偶数和奇数列表?在蟒蛇

  8. 8

    如何区分奇数和偶数之间的列表?

  9. 9

    如何在JavaScript中将数组拆分为单引号和逗号分隔列表

  10. 10

    如何在JavaScript中将数组拆分为单引号和逗号分隔列表

  11. 11

    如何在 Python 中将字符串拆分为列表?

  12. 12

    如何在Scala中将String转换为整数列表?

  13. 13

    将整数列表分为偶数和奇数和的交替组

  14. 14

    如何在Java中将列表字符串列表转换为列表整数列表

  15. 15

    偶数和奇数列表

  16. 16

    偶数和奇数列表

  17. 17

    如何将数组拆分为奇数数组和偶数数组

  18. 18

    如何递归查找整数列表中的最大元素?

  19. 19

    如何在C ++中将链接列表结构返回给main?

  20. 20

    如何将整数数组划分为偶数和奇数?

  21. 21

    给定条件奇数或偶数,如何对列表中的偶数或奇数求和?

  22. 22

    如何在python中将两个奇数列表添加到一个列表中?

  23. 23

    如何在Prolog中判断列表长度是奇数还是偶数

  24. 24

    如何在vb.net中将字符串拆分为列表/数组

  25. 25

    如何在SQL中将字符串拆分为列表以进行过滤?

  26. 26

    我如何在Java中将Shapes的ArrayList拆分为分区/列表(仅建议)

  27. 27

    如何在Python中将列表拆分为不同的字符串

  28. 28

    如何在python中将列表项换行符拆分为逗号

  29. 29

    如何在Haskell中将整数列表转换为真与假矩阵

热门标签

归档