Inserting elements in list, between every two

Question

I need to write a function that inserts a new node in a singly linked list, between every two existing nodes, with a value that is equal to the difference of the values of those two nodes.

For example if we have list 1→2→5→7 the result should be 1→1→2→3→5→2→7, because 2-1=1, 5-2=3 and 7-5=2.

Here is my attempt:

struct Node{
    int v;
    struct Node* next;
};
void insert(struct Node** headPtr){
    struct Node* curr = *headPtr;
    struct Node* new = malloc(sizeof(struct Node));
    while(curr->next!=NULL){
        new->v=curr->next->v-curr->v;
        new->next=curr->next;
        curr->next=new;
        curr=curr->next;
    }
}
void addRear(struct Node** headPtr, int v_new){
    struct Node* new = malloc(sizeof(struct Node));
    new->v=v_new;
    new->next=NULL;
    if(*headPtr==NULL){
        *headPtr=new;
    }else{
        struct Node* curr = *headPtr;
        while(curr->next!=NULL){
            curr=curr->next;
        }
        curr->next=new;
    }
}
void print(struct Node* head){
    struct Node* curr = head;
    while(curr!=NULL){
        printf("%d ",curr->v);
        curr = curr->next;
    }
}

But when I run the following in main, I don't get any result. Here is my main code:

struct Node* head=NULL;
addRear(&head,1);
addRear(&head,2);
addRear(&head,5);
addRear(&head,7);
print(head);
printf("\n");
insert(&head);
print(head);

Answer 1

Some issues:

• You are only creating one new node. Move the creation of the new node inside the loop.
• curr=curr->next is not correct, because then curr will become equal to the new node. And so in the next iteration you will not have come any closer to the end of the list. The loop will never end. Instead you should do curr = new->next.
• If the given list is empty, the evaluation of curr->next is invalid and leads to undefined behaviour. Add a guard for this boundary case.

Here is the corrected code:

void insert(struct Node** headPtr){
    struct Node* curr = *headPtr;
    if (curr == NULL) return; // <---
    while (curr->next != NULL) {
        struct Node* new = malloc(sizeof(struct Node)); // <---
        new->v = curr->next->v - curr->v;
        new->next = curr->next;
        curr->next = new;
        curr = new->next; // <---
    }
}