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

Question

我正在尝试使用递归（不是迭代）来反转链表。最初，我将 head 指针设置为全局变量，因此我不需要 return 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

是否有任何其他方法可以通过引用变量传递来实现它？另外，您能解释一下为什么第二个代码会像现在这样输出吗？谢谢！编辑： 所以这似乎不是一个很好的方法。所以我能想到的最后一种方法是通过值参数传递和 return 结果（假设 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
}

但我想不出解决 "control may reach end of non-void function" 问题的方法。有帮助吗？

Answer 1

一个简单的解决方案：您可以在 Reverse:

中调用您的第一个函数

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

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

How to reverse a linked list using one pass by reference variable?

c++

linked-list

pass-by-reference