Chained list in C - Reversing nodes recursively

Question

I’m following the notes of Algorithm Projects by Professor Paulo Feofiloff, and I’m having a hard time solving a question from the Chained Lists, transcript to follow:

Exercises 5

7. Write a function that inverts the order of cells in a chained list (the first becomes the last, the second becomes the penultimate etc.). Do this without using auxiliary space, just changing pointers. Give two solutions: an iterative and a recursive.

I was able to come up with an iterative solution, but I couldn’t even draw a recursive solution.

So I ask you to direct me to the recursive solution of this problem. Thank you!

Follow iterative solution code (please indicate improvements).

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node *next;
} NODE;

/*
Esta função recebe uma lista encadeada de inteiros e inverte a posição das
células desta lista usando apenas ponteiros. Ex.: o primeiro nó troca de lugar 
com o último, o segundo nó troca de lugar com o antepenúltimo, etc. 
*/

// versão iterativa
void swap_nodeI (NODE **head) {
    // if list is empty or there is only one node, nothing to do
    if (*head == NULL) return;

    // declare variables for first half of the list
    NODE *prevX = NULL, *currX = *head;
    int countX = 1;

    // declare variables for second half of the list
    NODE *prevY = NULL, *currY = *head; 
    int countY = 1;

    // count nodes (countY)
    for (; currY->next != NULL; currY = currY->next, ++countY);

    // swap nodes
    NODE *temp;
    int i, j;
    while (countX < countY) {

        // setup pointers
        for (currY = *head, i = 1; i != countY; ++i) {
            prevY = currY;
            currY = currY->next;
        }
        for (currX = *head, j = 1; j != countX; ++j) {
            prevX = currX;
            currX = currX->next;
        }

        // swap X and Y
        if (prevX != NULL) prevX->next = currY;
        else *head = currY;
        if (prevY != NULL) prevY->next = currX;
        else *head = currX;
        temp = currY->next;
        currY->next = currX->next;
        currX->next = temp;

        // update counters
        ++countX;
        --countY;
    }
}

Answer 1

After realizing that the strategy of reversing the list meets the statement, everything cleared. I was focused on treating the equidistant pairs of the list, making the solution difficult. Even the iterative solution would be much simpler:

void reverse(NODE **head) {
    NODE *prev = NULL;
    NODE *curr = *head;
    NODE *next;

    while (curr != NULL) {
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    *head = prev;
}

Follows recursive solution:

void reverseR(NODE **head) {

    /* Tratar lista vazia */
    if (*head == NULL) return;

    /* Atribuir um ponteiro para o nó atual
       e outro ponteiro para o restante da lista */
    NODE *curr;
    NODE *rest;
    curr = *head;
    rest = curr->next;

    /* Retornar ao chegar no final da lista */
    if (rest == NULL) return;

    /* Chamar a recursão até atingir o final da lista */
    reverseR(&rest);

    /* Inverter os nós e acertar a cabeça da lista */
    curr->next->next = curr;
    curr->next = NULL;
    *head = rest;
}