Solution

1. Reverse the Linked List.

static void Reverse(struct node** headRef) {

struct node* result = NULL;

struct node* current = *headRef;

struct node* next;

while (current != NULL) {

next = current->next; // tricky: note the next node

current->next = result; // move the node onto the result

result = current;

current = next;

}

*headRef = result;

}

2. Reverse the Linked List recursively.

void RecursiveReverse(struct node** headRef) {

struct node* first;

struct node* rest;

if (*headRef == NULL) return; // empty list base case

first = *headRef; // suppose first = {1, 2, 3}

rest = first->next; // rest = {2, 3}

if (rest == NULL) return; // empty rest base case

RecursiveReverse(&rest); // Recursively reverse the smaller {2, 3} case

// after: rest = {3, 2}

first->next->next = first; // put the first elem on the end of the list

first->next = NULL; // (tricky step -- make a drawing)

*headRef = rest; // fix the head pointer

}