Part 20 of 22 in Linked List - set 01

## Insert Node at nth position in a linked list by admin

Problem statement

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.

Input

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.

Output

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