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.
InputYour 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.
OutputReturn 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.
malloc(C)
or new(C++)
and put in our data and point the next pointer of that node towards NULL
.NULL
or not,if it is then our newly created node becomes our head and we'll return it.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.// Pointing ToBeInserted to the next node of Traverse ToBeInserted -> next = traverse -> next; // Now pointing traverse towards our New Node traverse -> next = ToBeInserted;
// 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;
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