Finding and removing the last occurrence of an element in a (singly) linked list with only one traversal

Question

Is it possible to find the last occurrence of an element (for example, an integer) and remove this node with only one (forward) traversal through the list?

Answer 1

Yes.

Simply remember the previous entry every time you find the value you're searching for on the traversal. When the traversal is complete, the last entry remembered will have a link to the entry to be removed, and that is sufficient to do the removal.

Answer 2

public void DeleteLastOccurenceOfKey(Node head, int key) 
{
    Node current=head;
    Node prev=null;
    Node temp=null;

    while(current!=null)
    {
        if(current.next!=null && current.next.data==key)
        {
        prev=current;
        temp=current.next;
        }
        current=current.next;
    }
    prev.next=temp.next;

}

DeleteLastOccurenceOfKey(head,25);

I/P:5 10 15 25 35 25 40 O/P:5 10 15 25 35 40

Answer 3

/*
 * Delete last occurrence of an item from linked list
 * Given a liked list and a key to be deleted. Delete last occurrence of key
 * from linked. The list may have duplicates.
 *
 * Examples:
 *
 * Input:   1->2->3->5->2->10, key = 2`enter code here`
 * Output:  1->2->3->5->10
 */


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

typedef struct list_ list;
struct list_ {
    int d;
    list *next;
};


void insert (list **head, int d) {
    list *tmp = (list *)malloc(sizeof(list));
    assert(tmp);
    tmp->d = d;
    tmp->next = *head;
    *head = tmp;
}

void printL (list *p) {
    while (p) {
        printf (" %d ", p->d);
        p = p->next;
    }
    printf ("\n");
}


void deletlastOccurence (list **head, int d) {

    list *cur = *head;
    list *prev = NULL;
    list *match = NULL;

    if (cur == NULL) {
        printf ("list is empty\n");
        return;
    }

    /*
     * Special case when there only ONE NODE
     * in the LIST
     */
    if (cur->next == NULL) {
        if (cur->d == d) {
            printf ("Deleted one node %d\n", cur->d);
            free(cur);
            *head = NULL;
        } else {
            printf(" No match\n");
        }
        return;
    }

    /*
     * Keep track of previous node
     */
    while (cur && cur->next) {

        if (cur->next->d == d) {
            prev = cur;
            match = cur->next;
        }
        cur = cur->next;
    }

    if (prev){
        prev->next = match->next;
        printf ("Delete %d\n", match->d);
        free (match);
    } else {
        /*
         * Special case when the last node is
         * on the head itself
         */
            if ((*head)->d == d) {
            cur = *head;
            *head = cur->next;
            printf("element is at head Delete %d\n", cur->d);
            free (cur);
        } else {
            printf ("No match\n");
        }
    }

    printL(*head);
}




int main (int argc , char *argv) {

    list *h = NULL;
    insert(&h, 1);
    insert(&h, 2);
    insert(&h, 3);
    insert(&h, 4);
    insert(&h, 5);
    insert(&h, 2);
    insert(&h, 1);
    insert(&h, 6);
    printL(h);
    deletlastOccurence(&h, 6);
    deletlastOccurence(&h, 2);
}