1

我试图反转一个链表，但是每当我执行以下函数时，我只得到最后一个元素。例如，如果列表之前包含 11、12、13。执行该函数后，它只包含13个。请指出我代码中的错误

void reverselist() {
    struct node *a, *b, *c;
    a = NULL;
    b = c = start;

    while (c != NULL) {
        c = b->next;
        b->next = a;
        a = b;
        b = c;
    }
    start = c;
}
4

4 回答 4

1
  1. 您的循环保护是否确保 start 为空？
  2. 如果您不使用 start 来标识列表的第一个元素，那么您正在使用的变量仍然指向第一个元素，现在是最后一个元素。
于 2012-07-17T11:30:37.910 回答
0

我会做一个前置函数，并完成以下操作：

struct node* prepend(struct node* root, int value)
{
    struct node* new_root = malloc(sizeof(struct node));
    new_root->next = root;
    return new_root;
}

struct node* reverselist(struct node* inlist)
{
    struct node* outlist = NULL;

    while(inlist != NULL) {
        struct node* new_root = prepend(outlist, inlist->value);
        outlist = new_root;
        inlist = inlist->next;
    }

    return outlist;
}

没有测试过这个，但猜你掌握了它的想法。可能只是你的变量名，它没有描述任何内容，但我认为这种方法更清晰，更容易理解实际发生的情况。

编辑：

有一个问题为什么我不就地做，所以我会在这里回答：

  1. 你能就地做吗？您确定不想保留原始列表吗？
  2. 你需要就地做吗？malloc 是否耗时/这是代码的性能关键部分吗？请记住：过早优化是万恶之源。

事情是，这是第一个实现。它应该工作，而不是优化。它还应该在考虑这个实现之前编写一个测试，并且你应该保持这个缓慢的、未优化的实现直到测试通过，并且你已经证明它对你的使用来说很慢！

当您通过了单元测试并证明实现速度很慢时，您应该优化代码，并确保它仍然通过测试，而不更改测试。

另外，答案是否有必要就地操作？在恢复它之前分配内存怎么样，这样你只有一个分配调用，并且应该希望得到一个很好的性能提升。

这样每个人都很高兴，您的代码更简洁，并且避免了 Bob 叔叔拿着猎枪出现在您家门口的风险。

于 2012-07-17T11:41:52.083 回答
0 
// 你应该假设 Node 有一个名为 next 的 Node*
// 指向列表中的下一项
// 如果成功则返回反向列表的头部，否则为 NULL / 0
节点 *reverse( 节点 *head )
{
    节点 *prev = NULL;

    而（头！= NULL）
    {
        // 保存下一个，因为我们将销毁它
        节点 *next = head->next;

        // 下一个和上一个现在颠倒了
        头->下一个=上一个；

        // 遍历列表
        上一页=头；
        头=下一个；
    }
    返回上一个；
}
于 2012-07-17T12:01:39.177 回答
0

c 是一个辅助指针。

void reverselist()
{
    struct node *a, *b, *c;
    a=NULL;
    b=start;
    while(b!=NULL)
    {
        c=b->next
        b->next=a;
        a=b
        b=c
    }
    start=a;
}
于 2012-07-17T14:24:31.353 回答