Recursively reverse a linked list in C

March 2, 2023

Given the struct ListNode:

typedef struct _listnode
{
    int item;
    struct _listnode *next;
} ListNode;

how to recursively reverse a linked list using a function with void return type and single parameter for passing in the address pointing the head ListNode of the linked list? (note that the function should not have a return type; the reversed linked list is accessible from the outside of the function so that the elements can be printed)

void reverseList(ListNode **headptr)
{
    if ((*headptr) == NULL)
        return;

    ListNode *first = *headptr;
    ListNode *rest = first->next;

    if (rest == NULL)
    {
        *headptr = first;
        return;
    }

    reverseList(&rest);

    rest->next = first;
    first->next = NULL;
}

Apparently the code above only returns the first element of the original list, without being reversed, while the remaining elements are gone.

>Solution :

The problem with your function implementation is that in this call

reverseList(&rest);

the function changes the local variable rest

ListNode *rest = first->next;

instead of changing the data member first->next.

So in this if statement

if (rest == NULL)
{
    *headptr = first;
    return;
}

the local variable declared in the previous recursive call of the function is changed. You need to pass to each recursive call of the function the pointer to the original head node through pointer to it.

And you function has too many return statements.

The function can look the following way:

void reverseList( ListNode **head )
{
    if (*head && ( *head )->next)
    {
        ListNode *last = *head;

        *head = ( *head )->next;

        reverseList( head );

        last->next->next = last;
        last->next = NULL;
    }
}