relyMATE relyMATE - 1 month ago 22
C Question

Deleting Consecutive Element in a Linked List

Given the following definition of linked-list

typedef struct elemento {
int inf;
struct elemento *next;
} lista;


I'm trying to create a function


lista *SeekAndDestroy(lista *p, int k);


that, given a list *p and a positive integer k, which searches on the list, the first sequence of consecutive elements whose sum is exactly k and eliminate such elements from the list.

My try:

lista *SeekAndDestroy(lista *p, int k) {
lista *a, *nuovo;
int x = 0;

a = (lista *)malloc(sizeof(lista));
a->inf = p->inf;
nuovo = a;
p = p->next;

while (p != NULL) {
if (p->next != NULL) {
if ((p->inf + p->next->inf) == k) {
if (x != 1) {
p = p->next->next;
x = 1;
continue;
}
}
}
nuovo->next = (lista *)malloc(sizeof(lista));
nuovo = nuovo->next;
nuovo->inf = p->inf;
p = p->next;
}
nuovo->next = NULL;
return a;
}


This my solution has two main problems:

1) erases a maximum of two consecutive elements and not more

2) if the items to be deleted are the first two, the function does not work
How can i solve this problem? Thanks

Answer

Here's a function I wrote to tackle the two problems faced by you and any other boundary conditions:

list* Seek_Destroy(list* head, int target){
    if(head == NULL)
        return NULL;
    list* temp = head;
    bool find_complete = false;

    list *prev = temp;
    //Loop for iterating until list is complete or target sum is found.
    while( !find_complete){
        //Create a pointer for loop calculations
        list* sum_loop = temp;
        //Initialize sum to 0
        int sum =0;
        //Loop for checking whether the sum is equal to the target
        while(sum <= target && sum_loop->next!= NULL){
            //Keep adding the sum
            sum += sum_loop->inf;

            if(sum == target){
                //Set the flag for exiting outer loop
                find_complete = true;
                //Test whether head of the list is included in the sum
                if (temp == head){
                    //Make head point to the struct after the last element included in the sum loop
                    head = sum_loop->next;
                    //Delete and free memory
                    while(temp!= sum_loop){
                        list* del = temp;
                        temp = temp->next;
                        free(del);
                    }
                }else {
                    //Set the next pointer of previous element  of the list to point after the last element included in the sum loop
                    prev->next= sum_loop->next;
                    //Delete and free memory
                    while(temp!= sum_loop){
                        list* del = temp;
                        temp = temp->next;
                        free(del);
                    }
                }           
            break;
            }
            //Increment the pointer for the sum calculation         
            sum_loop = sum_loop->next;
        } 
        prev = temp;
        //Make temp point to next element in the list
        temp = temp->next;
        //IF entire list is traversed set the flag to true
        if (temp ==NULL){
            find_complete = true;
        }       
    }

    return head;
}