recursion - C - linked list reverse recursively: why use double pointer?

Question

I understand the logic when the struct Node *head is a global variable.

However, when I do the reverse using struct Node *head as a local variable in main(), I have to use double-pointer and pointer of Head, and I don't understand where exactly I have to place them.

void Reverse(struct Node *Head, struct Node **headpointer) {
    struct Node *first;
    // when the list is empty
    if (Head == NULL)
        return;

    first = Head;
    // when there is one node left
    if (first->next == NULL) {
        *headpointer = first;
        return;
    }

    Reverse(first->next, headpointer);

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

I am unclear why I have to use...

first = Head;
*headpointer = first;

why can't I just use

Head = first? 

Also, if first = Head line in front of the recursive function call Reverse(first->next, headpointer), don't the first->next value also equal to Head which points to the first node?

Is there any good logical diagram/pic/explanation/examples that can explain this difference?

Answer 1

I am unclear why I have to use... first = Head

Actually, the first variable isn't needed in this code at all. It is just a copy of Head, so to simplify you can just replace the variable with Head. Everything will work the same without it:

if (Head == NULL)
  return;

if (Head->next == NULL) {
  *headpointer = Head;
  return;
}

Reverse(Head->next, headpointer);

Head->next->next = Head;
Head->next = NULL;

I am unclear why I have to use... *headpointer = Head

The Head variable is the pointer to the head of the list you want to reverse, and the function stores the head of the newly reversed list into *headpointer. It does this because Head is just a copy of the pointer that was passed in to the Reverse() function, so updating its value won't change the original pointer; that's why a separate double pointer variable is used.

why can't I just use Head = first?

Head is a copy of the pointer that was passed to the function. Updating the Head pointer will not update the original list pointer that you passed in. Also, as I said before, Head is the same as first, so an assignment like that does nothing.

Also, if first = Head line in front of the recursive function call Reverse(first->next, headpointer), don't the first->next value also equal to Head which points to the first node?

first->next (or Head->next) is just the next node in the list. The purpose of the function call is to reverse the rest of the list first, and then place Head (or first) at the end of the list (which is what the last two lines do).