c++ - 如何使用引用变量一次传递来反转链表？

Question

我正在尝试使用递归(不是迭代)来反转链表。最初，我将 head 指针设置为全局变量，因此不需要返回 head。这个版本工作正常，所以我想实现一个将 head 作为局部变量的版本。代码如下:

void Reverse(node* &head, node *p)
{
    if(p == NULL) return; //nothing in list
    if(p->link == NULL)
    {
        head = p;
        return;
    }
    Reverse(head, p->link);
    node *q = p->link;
    q->link = p;
    p->link = NULL;
}
//some code to set local var head to a linked list
Reverse(head, head);

工作正常，但看起来太麻烦了。我已经尝试了一些方法来只用一个变量来做到这一点，但它不起作用。

void Reverse(node* &head)
{
    if(head == NULL) return;
    node *p = head;
    if(p->link == NULL)
    {
        head = p;
        return;
    }
    Reverse(p->link);
    node *q = p->link;
    q->link = p;
    p->link = NULL;
}
//some code to set local var head to a linked list
Reverse(head);
Print(head); //output only last element in list

是否有任何其他方法可以通过引用变量传递来实现它？另外，您能解释一下为什么第二个代码会像现在这样输出吗？谢谢!编辑:所以这似乎不是一个很好的方法。所以我能想到的最后一种方法是通过值参数传递并返回结果(假设 head 是本地的)。我尝试这样实现它:

node* Reverse(node *p)
{
    if(p == NULL) return p; //nothing in list
    if(p->link == NULL)
    {
        return p;
    }
    Reverse(p->link);
    node *q = p->link;
    q->link = p;
    p->link = NULL;
    //control may reach end of non-void fucntion
}

但我想不出一种方法来解决“控件可能到达非 void 函数的末尾”问题。有帮助吗？

Answer 1

一个简单的解决方案:您可以在 Reverse 中调用您的第一个函数:

void Reverse(node *&head) {
    Reverse(head, head); //may want to rename or make private
}