Recursively reverse a linked list in O(n) time and O(1) memory.
(O(n) Depending on if you count recursive stack in the equation)
Let's start off whith what is O(n) time and O(1) memory.
O(n) time means it will only take the n number of iterations to complete the task for example if the list is of length 5 then only five actions will take place.
O(1) memory means that no more structers need to be created to accomplish this task you are only using what memory you have and rearranging the pointers.
Making new pointers is acceptable though.
Lets get started!
Like all recursive functions we need to start with a base case(s).
The simplest case we will have is checking for NULL, simply states we have passed in an empty list so we should return NULL.
if (list == NULL) return NULL;
A kind of odd thing about this problem is that we need a second case for checking if we are at the last node before NULL.
This is because we still want NULL to be at the end of the list and the rest be reversed.
if (list->next == NULL) return list;
So now we will store our old pointer and call recursion on our new.
The basic idea here is that we want to take the list and reverse the 'next' pointers to point the other way, but the trickey part is we need to manage the orinal list.
The recursive part will go down to the base case at the end of the list and work it's way back up, changing the pointers as it goes.
The key here is that we will store the old value of next before we call the recursive part so it's still in our stack when the recursion is working its way back up.
node* next = list->next;
node* rev = reverse_list(list->next);
Finally we will actually change our pointer and handle the end of our new list.
Here we are setting the next->next which is accesing our next pointers ... next pointer and pointer it backwards.
Finally we will return our reversed list's head.
next->next = list;
list->next = NULL;
return rev;
Here is the final function
node* reverse_list(node* list) {
if (list == NULL) return NULL;
if (list->next == NULL) return list;
node* next = list->next;
node* rev = reverse_list(list->next);
next->next = list;
list->next = NULL;
return rev;
}