Why Linked lists ?
While programming in C language, one of the biggest constraint comes in allocation of memory for the data you are required to save. The memory allocation can be done using two different methods generally termed as static memory allocation and dynamic memory allocation.
If the size of the data is already known, the best option is static memory allocation using arrays for saving lists but if you don’t know the size of data to be saved in the list, then Using static memory allocation like arrays cannot serve for the purpose.
What is linked lists?
Linked lists serve the purpose of saving the data of unknown size during the runtime. They make use of the pointers to keep track of the location of the saved data. Generally the elements of linked lists are structures which can store necessary data along with a space to save the pointer of the data next in the list.
Hence we only require keeping track of the first elements pointer and the rest of the data is connected to each other using the pointers in the structure which correspond to the next memory location of the data.
How to Reverse the Linked list using recursion algorithm?
To know how to reverse the linked list using recursion in c programming without losing the information, the recursion can serve as the most efficient way. First, to make a recursive algorithm, we need to understand how the present data in the list is being held. To reverse the linked list, we only need to reverse the pointers directions of the list. So in every loop, we require a temporary pointer variable to save the start location while the list is being reversed.
struct node *reverse(struct node *head
{
struct node *tail;
if (head == NULL || head->link == NULL)
{
return head;
}
tail = reverse(tail->link);
head->link->link = head;
head->link = NULL;
return tail;
}
Once the start pointer is stored in temporary pointer, write recursive code for swapping the pointers from the end. Firstly reassign the start pointer to the end location data, then decrement the counter in a loop and continue swapping pointers by assigning the “i-1th”pointer to the current ith pointer.
At the end of the recursive process, assign the second last entry of the list (in reversed order) the value of the temporary pointer and put a null pointer in the last pointer location. Finally user linked list has been reversed using a recursive c program.
