Deleting Consecutive Element in a Linked List

Question

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 1

Assuming your numbers are all non-negative, there's a more efficient algorithm you can use. You simply run two pointers, ptrA and ptrB, through the list, maintaining the sum of the inclusive elements.

If the sum isn't what you need, you do one of two things. First, if your current sum is less than that needed, bring the next element into the array by advancing ptrB.

If your current sum is more than what you need, you take out the first element in your range by advancing ptrA. Both these operations should, of course, adjust the current range sum. There's an edge case here in that you don't want to do this if there's currently only one item in the range.

And it should go without saying that, if the current range sum is equal to what you need, you simply delete that range and exit.

In terms of pseudo-code, it would be something like:

def delExact(list, desiredSum):
    # Check non-empty and start range.

    if list is empty:
        return
    ptrA = list.first
    ptrB = ptrA
    rangeSum = ptrA.value

    # Continue until match found

    while rangeSum is not equal to desiredSum:
        # Select add-another or remove-first.

        if ptrA == ptrB, or rangeSum < desiredSum:
            # Need to bring another in, returning if list exhausted.

            ptrB = ptrB.next
            if ptrB == null:
                return
            rangeSum = rangeSum + ptrB.value
        else:
            # Need to remove one.

            rangeSum = rangeSum - ptrA.value
            ptrA = ptrA.next

    # If we exit the loop, we've found a sum match.
    # Hence we need to delete ptrA through ptrB inclusive.

---

However, that two-pointer approach breaks down if negative numbers are allowed since you don't actually know what effect later elements may have.

In that case, you basically have to do an exhaustive search of all possibilities, and that basically boils down to:

for each element in list:
    for each possible segment from that element on:
        check and act on summed data

That's actually more of an English representation, the pseudo-code for such a beast would be along the lines of:

def delExact(list, desiredSum):
    # For each list element.

    ptrA = list.first
    while ptrA is not null:
        # For each possible segment starting at that element.

        segmentSum = 0
        ptrB = ptrA
        while ptrB is not null:
            add ptrB.value to segmentSum

            # Delete segment if sum matches, then return.

            if segmentSum is equal to desiredSum:
                # Here we delete from ptrA through ptrB inclusive.
                return

            # Otherwise, keep adding elements to segment.

            ptrB = ptrB.next

        # No matching segment, move on to next element.

        ptrA = ptrA.next

    # No matching segment at any element, just return.

---

The use of either of those algorithms will solve your problem regarding only deleting two elements.

The problem of deleting at the start of the list is to simply recognise that fact (ptrA == list.first) and make sure you adjust the first pointer in that case. This is a standard edge case in linked list processing, and can be implemented as something like:

def deleteRangeInclusive(list, ptrA, ptrB):
    # Adjust list to remove ptrA/ptrB segment,
    #   allowing for possibility ptrA may be the head.

    if ptrA == list.first:
        list.first = ptrB.next
    else:
        beforeA = list.first
        while beforeA.next != ptrA:
            beforeA = beforeA.next
        beforeA.next = ptrB.next

    # Now we can safely remove the ptrA-ptrB segment.

    while ptrA != ptrB:
        tempA = ptrA
        ptrA = ptrA.next
        delete element tempA
    delete element ptrB

Answer 2

I solved like that:

Lista *Distruggi(Lista *p, int k) {
    Lista *n = NULL, *nuova = NULL;
    int z = 0;
    for (Lista *i = p; i != NULL && z != 1; i = i->next) {
        for (Lista *j = i; j != NULL; j = j->next) {
            int sum = somma(i, j);
            if (sum != k) continue;

            n = (Lista *)malloc(sizeof(Lista));
            n->inf = p->inf;
            p = p->next;
            nuova = n;

            while (p != i) {
                nuova->next = (Lista *)malloc(sizeof(Lista));
                nuova = nuova->next;
                nuova->inf = p->inf;
                p = p->next;
            }

            while (j != NULL) {
                nuova->next = (Lista *)malloc(sizeof(Lista));
                nuova = nuova->next;
                nuova->inf = j->inf;
                j = j->next;
            }
            z = 1;
            break;
       }
    }
    if (z == 0) return p;//NO CHANGE
    else {//CHANGE
        nuova->next = NULL;
        return n;
    }
}

Answer 3

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

Answer 4

For now, let's forget about linked list and pointer and stuffs. Say, we have to solve the problem for a given array. Can we do that? Sure!

for (int i = 0; i < array.length; ++i) {
    for (int j = i; j < array.length; ++j) {
        int sum = getRangeSum(array, i, j);
        if (sum != k) continue;

        // construct new array and return
    }
}

This code can be optimized further but let's keep it simple for now. So, in linked list, similar approach can be used. And the delete part is also simple. You can keep a variable to keep track of the previous node of i. Let's call it iParent. Now, we can remove the [i, j] segment as iParent->next = j->next.

Obviously, you need to consider some corner cases like if such segment is not found or if the segment starts from the beginning of the linked list etc.