These type of functions are a learning exercise, as opposed to being a practical solution (an iterative method would not have the potential for stack overflow and would be faster).
if(*head == NULL) check is only needed for the initial call. The code checks for next == NULL and returns instead of calling itself again.
first->nseg->nseg = first reverses the next (nseg) pointers in the list. Looking at the initial instance (first call) to recursiveReverse(), then first = *head = pointer to first node. first->nseg = pointer to second node, first->nseg->nseg = first sets the second nodes next (nseg) pointer to the first node. In the case of all but the initial call, first->nseg = NULL effectively does nothing, since it gets overwritten after returning to the previous call when it does first->nseg->nseg = first. In the case of the initial call, first->nseg = NULL sets the next pointer of what was the first node of the initial list is set to NULL.
During the recursion, rest is advanced until rest == NULL, in which case the function just returns without updating the prior instance of head/rest. So as the function returns back up the call chain to the initial call, all instances of rest will end up pointing to what was the last node of the original list, including the initial call when then sets head to point to what was the last node.
It might help to separate this into two functions, which gets rid of some unneeded checks and variables. Reverse is the initial function which calls recursiveReverse.
Code:
void Reverse(Node **head)
{
Node* first;
/* if 0 or 1 nodes, return */
if (*head == NULL || (*head)->next == NULL)
return;
first = *head; /* save ptr to first node */
recursiveReverse(head); /* reverse next pointers, set head to last node */
first->next = NULL; /* set what was first node's next ptr to NULL */
}
void recursiveReverse(Node** head)
{
Node* first;
first = *head; /* save ptr to current node */
if(first->next == NULL) /* if last node, return */
return;
*head = first->next; /* advance head to next node */
recursiveReverse(head); /* recurse until last node */
first->next->next = first; /* set next node's next pointer to current node */
}
Originally Posted by Salem
