递归反向链接列表

Question

我在链接列表中定义了一个节点:

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

我想以递归方式反转链接列表.我将头指针传递给函数.我的函数定义如下:

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;
}

我该怎么办？我已经实现了迭代方法.

Answer 1

它应该如下工作:

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:这个函数是尾递归的.因此,最先进的编译器应该能够将这种递归解决方案转变为更有效的迭代解决方案.

Answer 2

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


    current=head;
    rest=head->next;

    if(rest == NULL)
    {
        /* Wrong. Think about the simple case of a one-element list.
           Your code will return NULL as the reversed list. */
        //return rest;
        return current;
    }
    /* You lost the return value, which will be the beginning of the reversed 'rest'. */
    //reverseLinkedListRecursively(rest);
    rest = reverseLinkedListRecursively(rest);

    /* current->next points to the last element in the reversed 'rest'.
       What do you want that to point to? */
    //current->next->next=rest;
    current->next->next = current; // temporarily circular
    current->next=NULL;

    /* Now you can return rest, since you set it to the beginning of the reversed list. */
    return rest;
}