How can I insert a node in a singly linked list using recursion given: 1. a pointer to the head node 2. the index to insert the new node

Question

The function below is the one I am trying to work on. The problem I am running into is that I do not know how to "keep" the pointer to the original head to the list as that is what I have to return after insertion.

There is no Driver code so everything must be done inside this function.

Because I must do this recursively I cannot just create a temporary node to point to the original head. I am just getting used to recursion and I cannot find a solution.

NOTE: There are some other problems with my function as I believe it wouldn't work well for inserting a new node into the beginning and end of the linked list but I am confident I could work out those edge cases.

The main thing I am trying to learn is how to "store" the original head of my list.

All help is appreciated.

 Node* insert(Node* head, int index, int data)
{

if (head == NULL) return NULL; // if list is empty

if (index == 1) // if we have accessed node before insertion
{
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    new_node->next = head->next; // new_node->next now links to the node next in the list
    head->next = new_node; // head->next links to new node
    new_node->data = data; // assigns new node its data
    return head; // not sure how to return original head
}
return insert(head->next, index - 1, data);

}

Answer 1

//if you have created a node using class then here is the solution
//to insert a node at a position recursively

Node * insertRecursive(Node * head, int data , int key)
{
    if (head == NULL || key == 0)
    { 
        Node * newNode = new Node(data);
        newNode -> next = head;
        head = newNode;
    }
    else
    {
        head -> next = insertRecursive(head -> next , data , key - 1);
    } 
    return head;
}

Answer 2

//here is the full solution to add a node recursively at a position

#include<iostream>
using namespace std;

//the below code is for creation of class for node
class Node
{
    public:
        int data;
        Node * next;
    
    Node(int data) //constructor 
    {
        this -> data = data;
        next = NULL;
    }
};

//the below code is for creation of linked list 
//a terminator -1 is used to stop taking input
Node * takeInput()
{
    int data;
    cout<<"Enter the data of the node to be inserted ( use -1 to terminate 
    the insertion ) : ";
    cin>>data;
    Node * head = NULL;
    Node * tail = NULL;

    while(data != -1)
    {
        Node * newNode = new Node(data);
        if(head == NULL)
        {
            head = newNode;
            tail = newNode;
        }
        else
        {
            tail->next=newNode;
            tail = tail -> next;
        }
        cout<<"Enter the data of the node to be inserted ( use -1 to 
        terminate the insertion ) : ";
        cin>>data;
    }
    return head;
}

//the below code is to print the linked list
void print(Node * head)
{
    if(head == NULL)
    {
        cout<<"The linked list id empty !"<<endl;
        return;
    }
    Node * temp = head;
    while(temp != NULL)
    {
        cout<<temp->data<<" ";
        temp = temp -> next;
    }
    cout<<endl;
}

//the below part is the main solution to the problem 
//insertion at a position using recursion
Node * insertRecursive(Node * head, int data , int key)
{
    if (head == NULL || key == 0)
    { 
        Node * newNode = new Node(data);
        newNode -> next = head;
        head = newNode;
    }
    else
    {
         head -> next = insertRecursive(head -> next , data , key - 1);
    }
    return head;
}

//this is the main from where all the function calls happen
int main()
{
    int data, key;
    Node * head = takeInput();
    print(head);
    cout<<"Enter the data of the node to be inserted : ";
    cin>>data;
    cout<<"Enter the position of insertion : ";
    cin>>key;
    head = insertRecursive(head,data,key);
    print(head);
}

Answer 3

Node* insert_Node_recursively(Node* head,int data,int position){

//Inserting on the first node.
if(position==0){
    Node* newNode=new Node(data);
    newNode->next=head;
    head=newNode;
    return head;
}



if((head->next==NULL && position==0) /*for adding on the end of the list */   || position==1  /*Inserting on node in between */){
        Node* newNode=new Node(data);
        newNode->next=head->next;
        head->next=newNode;
        return head;
}
//in case the position exceeds the total number of nodes
if(head->next==NULL && position>0){
    return head;
}
else{
    head->next=insert_Node_recursively(head->next,data,position-1);
}

return head;   

}

this will work I think, covered all the aspects

Answer 4

Node *insertRecursive(Node* head,int pos,int val)
{
    if(pos==0 || head==NULL)
    {
        Node *newNode= new Node(val);
        newNode->next=head;
        head=newNode;
        return head;
    }
    else
        head->next = insertRecursive(head->next,pos-1,val);
    
}

Answer 5

For starters the parameter that specifies the position where a node has to be inserted should have an unsigned integer type, for example, size_t. Positions should start from 0.

The function can be defined the following way

struct Node * insert( struct Node *head, size_t pos, int data )
{
    if (head == NULL || pos == 0 )
    {
        struct Node *new_node = malloc( sizeof( struct Node ) );
        new_node->next = head;
        new_node->data = data;
        head = new_node;
    }
    else
    {
        head->next = insert( head->next, pos - 1, data );
    }

    return head;
}

Here is a demonstrative program

#include <stdio.h>
#include <stdlib.h>

struct Node
{
    int data;
    struct Node *next;
};

struct Node * insert( struct Node *head, size_t pos, int data )
{
    if (head == NULL || pos == 0)
    {
        struct Node *new_node = malloc( sizeof( struct Node ) );
        new_node->next = head;
        new_node->data = data;
        head = new_node;
    }
    else
    {
        head->next = insert( head->next, pos - 1, data );
    }

    return head;
}

void print( const struct Node *head )
{
    for (; head != NULL; head = head->next)
    {
        printf( "%d -> ", head->data );
    }
    puts( "null" );
}

int main( void )
{
    struct Node *head = NULL;

    head = insert( head, 0, 3 );
    print( head );

    head = insert( head, 0, 0 );
    print( head );

    head = insert( head, 1, 1 );
    print( head );

    head = insert( head, 2, 2 );
    print( head );
}

The program output is

3 -> null
0 -> 3 -> null
0 -> 1 -> 3 -> null
0 -> 1 -> 2 -> 3 -> null