recursion - Reversing a linkedlist recursively in c

Question

The following code works fine when head is sent as a parameter to it. As I am new to C, I couldn't understand how it works. Help me out please.

struct node *recursiveReverseLL(struct node *list)
{
    struct node *revHead;
    if (list == NULL || list->link == NULL)
    {
        return list;
    }

    revHead = recursiveReverseLL(list->link);
    list->link->link = list;
    list->link = NULL; 

    return revHead;
}

I dont know how the links are provided using those recursive calls. ie) if the links are as,

1 -> 2 -> 3 -> 4 

then hw is it changed as,

4 -> 3 -> 2 -> 1

Answer 1

The general recursive algorithm for this is:

1. Divide the list in 2 parts - first node and rest of the list.
2. Recursively call reverse for the rest of the linked list.
3. Link rest to first.
4. Fix head pointer

Here is the code with inline comments:

struct node* recursiveReverseLL(struct node* first){

   if(first == NULL) return NULL; // list does not exist.

   if(first->link == NULL) return first; // list with only one node.

   struct node* rest = recursiveReverseLL(first->link); // recursive call on rest.

   first->link->link = first; // make first; link to the last node in the reversed rest.

   first->link = NULL; // since first is the new last, make its link NULL.

   return rest; // rest now points to the head of the reversed list.
}

I hope this picture will make things clearer:

_{(source: geeksforgeeks.org)}
.