c++ - 我的链表反转递归方法代码有什么问题？

Question

我正在尝试使用递归来反转链表。当我在反转后显示列表时，我只得到原始列表的第一个元素 `

        void reve(node *a,node *b,node *c,node *h1)
       {
               if(c->next==NULL)
           {
               c->next=b;
               b->next=a;
                return ;
           }

           reve(a->next,b->next,c->next,h1);
           c->next=b;
           b->next=a;
           if(a==h1)
         {
            a->next=NULL;
         }

         return ;

      }` 

Answer 1

这是因为你的调用代码仍然持有一个指向曾经是第一个节点的指针，但那个节点现在是最后一个。
(至少如果代码确实有效——很难跟踪所有这些参数，而且它们的关系就像它们的名字一样神秘。)

如果你返回一个指向新头的指针，这会更容易实现。
您也只需要一 (1) 个参数。

然后你要处理三种情况:

1. 空列表——只返回空列表；
2. 单例列表——只需返回它；
3. 一般情况。

您可以通过首先反转列表的其余部分，接收新的头部来解决一般情况。

然后您需要使“新的最后一个元素”的next 指向“this”节点，以便使“this”节点成为反向列表的下一个元素。
这比听起来容易 - 您从递归中获得的反向列表中的最后一个节点仍然是该节点的 next 节点。
(不清楚的地方画在纸上)

然后您还需要通过清空其next 使“this”节点终止列表。

然后返回您从递归中收到的“新头”。

node* reverse(node* n)
{
    // Empty list:
    if (!n)
    {
        return nullptr;
    }
    // Singleton list:
    if (!n->next)
    {
        return n;
    }
    // General case:
    node* head = reverse(n->next); // Reverse the rest,
    n->next->next = n;             // Attach this node at the end,
    n->next = nullptr;             // Terminate the list,
    return head;                   // Done.
}