we know that pointer variable holds the address of the memory and Recursion is a looping technique in which a function calls itself . today we will see some of the concepts with pointers and recursion.
1. Inserting a new node into nth position from first in a single linked list.
we can solve this problem in many ways in O(n) time. now we solve the problem using recursion technique.
void insertNth(struct node** headref,int index,struct node* newnode);
As function parameters we pass headref as double pointer that means we are passing the reference of the address of head pointer so that we are linking the new node with reference to the address not with the value. If you do so the changes to the list will remain as expected.
Index is the index position starts from 0, and the new node is the node pointer which needs to added to the list at given index.
void insertNth(struct node** headref,int index,struct node* newnode)
{
static int i=0; // Reason we used i as static is it needs to initialize only once in recursion
if(((*headref) == NULL) || (i == index)){ //the loop using recursion technique will executes until these conditions are true
if(i != index)
return;
newnode->next=*headref;
*headref=newnode;
return;
}
i++;
insertNth(&(*headref)->next,index,newnode); // this is where the function calls itself nothing buy looping
}
look at the function calling
insertNth(&(*headref)->next,index,newnode);
the pointer of headref we mentioned something like this
&(*headref)->next
Structure of a node is as follows
struct node{
struct node* next;
int a;
};
*headref mentioned because we need to pass the address of the next pointer. so the meaning of the first parameter is : the value of the next pointer is an address, so the we are passing the address of the next pointer we are passing in the function. this loop continues untill either the headref is null or index is found.
in the next topic we shall see some more concepts of recursion techniques.
please share/comment if you like it..
Thanks & Regards
Kranthi Talluri
