Linked List element insertion at nth location

Question

I am trying to implement linked list in C and I have two different functions that are supposed to insert elements in the beginning and at nth position. My program crashes when it goes to the part where it starts executing the function to insert at nth position. Can someone please point out my mistake. Also the compiler tends to skip the last scanf statement (marked in the comments).

/****************************************************************
*Date: 12/30/2016
*This program adds an element to the beginning  and nth position
*of a linked list and then displays the elements in the list
*****************************************************************/


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



struct node
{
    int data;//Refers to the data part of the linked list
    struct node* next;//Refers to the pointer which points to the next element
};


/*************************************************************************************
Description   : This function is used to print the elements in the linked list
Input         : Pointer to the beginning of the linked list
Output        : N/A
*************************************************************************************/


void PrintElements(struct node *start)
{
    if(start==NULL)//If the list is empty
        printf("List is empty");
    else
    {
        while(start!=NULL)
        {
            printf("%d ",start->data);
            start=start->next;
        }
    }
}

/*************************************************************************************
Description   : This function is used to insert elements in the beginning of the
                linked list
Input         : Element to be inserted
Output        : N/A
*************************************************************************************/

struct node* InsertElementInTheBeginning(struct node *start, int x)
{
    struct node *new_node=(struct node*)malloc(sizeof(struct node));
    if(new_node==NULL)
    {
        printf("Memory allocation failed");
        return start;
    }
    new_node->data=x;
    new_node->next=start;
    start=new_node;
    return new_node;

}

/*************************************************************************************
Description   : This function is used to insert elements in the nth position of the
                linked list
Input         : Element and position to be inserted, pointer to beginning of linked
                list
Output        : N/A
*************************************************************************************/

struct node* InsertElementAtN(struct node *start,int x, int n)//Here the starting position for the linked list is assumed to be 1
{
    int i;
    struct node* new_node=(struct node*)malloc(sizeof(struct node));
    if(new_node==NULL)
    {
        printf("Memory allocation failed");
        return start;
    }
    new_node->data=x;
    new_node->next=NULL;
    if(n==1)
    {
        new_node->next=start;
        start=new_node;
        return start;
    }
    struct node *ptr;
    ptr=start;
    for(i=0;i<n-2;i++)
    {
        ptr=ptr->next;
    }

    new_node->next=ptr->next;
    ptr->next=new_node;
    return start;
}

int main()
{

    int x, n;
    struct node *HEAD;
    struct node *ptr;
    HEAD=NULL; //Assigning HEAD to null when there are no elements in the list
    ptr=NULL;
    printf("\n\rEnter numbers to be inserted into the list\n Press q to quit\n");
    while(scanf("%d",&x)==1)
    {
        HEAD=InsertElementInTheBeginning(HEAD,x);
        PrintElements(HEAD);
        printf("\n\rEnter numbers to be inserted into the list\n Press q to quit\n");
    }
        printf("\n\rEnter the number and position to be inserted");
        scanf("%d %d",&x,&n);//The compiler always skips this scanf no clue why
        HEAD=InsertElementAtN(HEAD, x, n);
        PrintElements(HEAD);

     //Freeing dynamic memory

    while(HEAD!=NULL)
    {
        ptr=HEAD;
        HEAD=ptr->next;
        free(ptr);

    }

    return 0;
}

Answer 1

I've always found something like this to be easier for me to understand (I'm assuming your positions must be 1 or more based on your code, unlike the usual C convention of 0 or more):

struct node *insertValueAt(struct node *head, int value, int position) {
    struct node *current;

    if (head == NULL || position == 1)
         return insertBefore(head, value);

    for (current = head; position > 1 && current->next != NULL; position--)
        current = current->next;

    current->next = insertBefore(current->next, value);

    return head;
}

Note that I used the name insertBefore, but your InsertElementAtTheBeginning does the same thing. The key to inserting a node N between to existing nodes A and B is to make A->next point to N that is returned from InsertElementAtTheBeginning(B, value).

Another thing to note is the unconditional insertion before a NULL node (i.e. at the beginning of an empty list or at the end of the list), regardless of the value of position because you can't insert an item at position 10 if you only have fewer than 4 items.

Answer 2

you should check that ptr->next is not NULL.

 for(i=0;i<n-2;i++)
 {
    if (ptr->next == NULL) return NULL;
    ptr=ptr->next;
 }

Answer 3

Add a getchar() after the first while loop in the main(). For explanation please check C: Multiple scanf's, when I enter in a value for one scanf it skips the second scanf.