如何使用一次通过引用变量来反转链表

Question

我试图用递归(不是迭代)来反转链表。最初，我设置我的头指针作为一个全局变量，所以我不需要返回头。这个版本工作得很好，所以我想实现一个将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
}

，但我不能想到一种方法来绕过"控制可能达到非空函数的结束"的问题。任何帮助吗?

Answer 1

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

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