CODEWITHSUNDEEP
crecursionreversesingly-linked-listfunction-definition
Centauri_42
Centauri_42

Reputation: 33

Recursively reverse a linked list in C

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.

Upvotes: 1

Views: 78

Answers (2)

Vlad from Moscow
Vlad from Moscow

Reputation: 311078

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

Upvotes: 1

trincot
trincot

Reputation: 350766

The issues:

  • The recursive call will make rest point to the node that originally was the tail of the list, so rest->next = first; is not right. rest is no longer pointing to what originally was the second node. Still, you have a reference to it with first->next, so you can use that and write:

    first->next->next = first;

  • You must assign to (*headptr) so it points to the node that was originally the tail. After the recursive call, you know what that node is: rest points to it, so end your function with:

    *headptr = rest;

NB: Not a problem, but your second if block does not need to do *headptr = first;, as these two pointers are already equal.

Upvotes: 0

Related Questions