反向链接列表递归 [英] Reverse Linked List Recursively

问题描述

我在链表定义为一个节点：

I have a Node defined in Linked List as:

typedef struct abc
{
    int id;
    struct abc *next;        
}node;

我要反向链接列表recursively.I想过去的头指针指向功能。我的函数的定义是这样的：

I want to reverse a Linked List recursively.I am passing the head pointer to the function. My function definition looks like:

node *reverseLinkedListRecursively(node *head)
{
    node *current;
    node *rest;
    if(head == NULL)
        return head;

    current=head;
    rest=head->next;

    if(rest == NULL)
    {
       return rest;
    }
    reverseLinkedListRecursively(rest);
    current->next->next=rest;
    current->next=NULL;
    return rest;
}

我应该如何进行？我已经实现了迭代的方法。

How should I proceed? I have implemented the iterative approach.

推荐答案

它应该工作如下：

node *reverseLinkedListRecursively(node *rest, node *reversed)
{
    node *current;

    if (rest == NULL)
        return reversed;

    current = rest;
    rest = rest->next;
    current->next = reversed;

    return reverseLinkedListRecursively(rest, current);
}

最初，在启动：

reverseLinkedListRecursively(linkedList, NULL);

BTW：此功能是尾递归。因此，国家的最先进的编译器应该能够把这个递归解决方案成为一个更高效的迭代求解。

BTW: This function is tail-recursive. So a state-of-the-art compiler should be able to turn this recursive solution into a more efficient iterative solution.

这篇关于反向链接列表递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！