递归地反转一个链表

Question

我正在尝试使用递归反转链表，我下面的代码

struct node* reverse_list(struct node *head)
    {
        struct node *temp=head,*rhead,*first;
        if (temp->next== NULL)
            return temp;
        else
        {
            first = head;
            rhead = reverse_list(temp->next);
            first->next = NULL;
            rhead->next = first;
            return rhead;
        }
    }

我找不到任何错误，但我仍然没有得到正确的输出。请帮助。

Answer 1

你需要两个连续的节点才能递归地完成:

struct node* reverse_list(struct node *head)
    {
       return reverse_list_prev(null, head);
    }
struct node* reverse_list_prev(struct node *prev, struct node *current)
    {
        if(null==current)
            return prev;
        struct node *tmp = current->next;
        current->next = prev;
        return reverse_list_prev(current, tmp);
    }

Answer 2

我觉得这行对我不太合适

     rhead->next = first;

在我看来，它应该遍历到rhead列表的末尾，tail指向first。