linked-listsingly-linked-list

Inserting elements in list, between every two


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);

Solution

  • Some issues:

    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; // <---
        }
    }