时间戳

首页 > 解决方案 > 如果 head 在 main 中本地声明，则链表的 void 递归反向函数的参数应该是什么？

c++ - 如果 head 在 main 中本地声明，则链表的 void 递归反向函数的参数应该是什么？

问题描述

我正在尝试实现链表的递归反转。除了提供 node* 指针作为参数之外，我还应该提供什么作为参数？

这个函数是当 head 在 main 中本地声明时。当全局声明 head 时，我成功实现了这个函数，因为我们不需要显式传递 head 的地址（因为它可以在函数内部访问）。 

#include<bits/stdc++.h>
using namespace std ;

struct node{
int data ;
node* link ;
};

void insert(int n, node** head)
{
node* temp = new node() ;
temp->link = NULL ;
temp->data = n ;
if(*head == NULL)
{
    *head = temp ;
}
else
{
    node* ptr = *head ;
    while(ptr->link != NULL)
    {
        ptr = ptr->link ;
    }
    ptr->link = temp ;
}
}

void print(node* ptr)
{   
while(ptr != NULL)
{
    cout<<ptr->data<<" " ;
    ptr = ptr->link ;
}
}

void reverse(node* ptr, node** hptr)
{   
node* temp = *hptr ;
if(ptr->link == NULL)
{
    *hptr = ptr ;
    return ;
}
ptr = ptr->link ;
reverse(ptr, &temp) ; //Line 10: Here is the main doubt. I want to write an equivalent of &head instead of &temp to pass the original address of head.
node* q = ptr->link ;
q->link = ptr ;
ptr->link = NULL ;
}

int main()
{   
node* head = NULL ; //local head declaration
insert(5,&head) ;
insert(6,&head) ;
insert(7,&head) ;
insert(8,&head) ;
reverse(head,&head) ;
cout<<endl ;
print(head) ;
}

当链表为 5->6->7->8 时，我打印这个链表时没有错误，也没有打印任何内容。预期的答案是 8->7->6->5 。如何纠正第 10 行或代码中的任何其他错误？

带全局头的代码：

#include<iostream>
using namespace std ;

struct node{
int data ;
node* link ;
};

node* head ;

void reverse(node* ptr) //pointer to node
{
if((ptr->link) == NULL) //exit condition
{
    head = ptr ;
    return;
}

else
{
    reverse(ptr->link) ;
    node* q = ptr->link ; //temp variable that points to the adjacent(right) node of ptr 
    q->link = ptr ;
    ptr->link = NULL ;
}

}

void print(node* ptr)
{
if (ptr == NULL)
{
    return ;
}
else
{
    cout<<ptr->data<<" " ;
    ptr = ptr->link ;
    print(ptr) ;
}

}

int main()
{
head = NULL ;
for(int i=0;i<4;i++)
{
    node* temp = new node() ;
    temp->link = NULL ;
    temp->data = i ;
    if(head == NULL)
    {
        head = temp ;
    }
    else
    {
        node* p = head ;
        while(p->link != NULL)
        {
            p = p->link ;
        }
        p->link = temp ;
    }

}

reverse(head) ;
print(head) ;


return 0 ;
}

标签： c++recursionlinked-listreverse

解决方案

这个版本适合我

void reverse(node* ptr, node** hptr)
{   
    if (ptr->link == NULL)
    {
        *hptr = ptr;
        return;
    }
    reverse(ptr->link, hptr);
    node* q = ptr->link;
    q->link = ptr;
    ptr->link = NULL;
}

ptr = ptr->link;上面版本的问题是递归调用之前的赋值。加上对头指针的错误处理。

推荐阅读