Given pointer to the head of a linked list and a number n = desired position, insert an element at position n from the beginning in the linked list.

Your method will be passed pointer to the linked list, the value of node and position at which the node has to be inserted on a 0-based index. The linked list could also be empty i.e it may not have any Node at all. You must take care of this.

Return pointer to the head of the linked list (modified).

Here We have to insert a node in a linked list at Nth position from starting.

• Firstly we create a node using malloc(C) or new(C++) and put in our data and point the next pointer of that node towards NULL.
• We firstly check if our head is NULL or not,if it is then our newly created node becomes our head and we'll return it.
• If not,then we check if the given N is 0 or not,if it is then address of our node becomes our new head and and it's next is pointed towards the head which we accept it as our parameter.
• If not,then We traverse to the Nth position where we have to insert our node.
• We first point our next pointer of the newly created node towards the next of the Nth positioned node in the linked list.
• Now these two points towards the same node.
• Now, we position the next of Nth node towards our node.
• And node is inserted.

 
      // Pointing ToBeInserted to the next node of Traverse
      ToBeInserted -> next = traverse -> next;

       // Now pointing traverse towards our New Node
       traverse -> next = ToBeInserted;

• But DON'T swap these two steps because then you will loose the address of the list after Nth positioned Node or for safety you can save it's address before so that you don't put yourself in that condition.
• For Example Doing like that

 
          // Firstly Address of node of next to Nth
          Node *ToStoreNext = traverse->next;

          // Pointing traverse towards new node
          traverse->next = ToBeInserted;

          //Pointing new node towards the rest of list
          ToBeInserted->next = ToStoreNext;

• For better understanding,Watch this video Here on our Youtube Channel.

editorial written by ishabh

/*
  Insert Node at a given position in a linked list
  The linked list will not be empty and position will always be valid
  First element in the linked list is at position 0
  Node is defined as
  struct Node
  {
     int data;
     struct Node *next;
  }
*/
Node* InsertNth(Node *head,int data, int position) // n is position from beginning
{
    // Node to be inserted in given position
    Node *ToBeInserted;

    // Allocating Memory
    ToBeInserted = new Node;

    // Filling the Data to New Node
    ToBeInserted -> data = data;
    ToBeInserted -> next = NULL;

    // It might be our First Node in Linked List
    if(head == NULL) {

        //Address of New Node Becomes our head
        return (head = ToBeInserted);
    } 
    
    // Node Might to be inserted At Head
    else if(position == 0) {
        // Joining previous Linked List After new Node
        ToBeInserted -> next = head;

       // Address of New Node Becomes our head
        return (head = ToBeInserted);
    } 

    // Inserting At Nth position
    else {
       
        int DistFromHead = 1;
       
        // Pointer to store intermediate address of node
        // To be used in Traversing
        Node *traverse = head;
      
        // Traversing to insert at Nth position
        while(traverse != NULL) {

            if(DistFromHead == position) {

                // Pointing ToBeInserted to the next node of Traverse
                ToBeInserted -> next = traverse -> next;

                // Now pointing traverse towards our New Node
                traverse -> next = ToBeInserted;

                // Returning Head as soon as we have inserted our new node
                return head;
            }
            traverse = traverse -> next;
            DistFromHead++;
        }
    }
}

featured solution by ishabh